Спираль Улама (Спираль простого числа) - PullRequest
Новая
       8

Спираль Улама (Спираль простого числа)

2 голосов
/ 20 августа 2009

Я ищу идеи / код (желательно C #, но работают и другие языки) для создания Спирали Улама бесконечно большого размера (ограничено продолжительностью работы программы или до ее остановки).

alt text

Теперь числа являются простыми числами, поэтому их код не имеет значения. Интересная часть состоит в том, как кодировать расположение в постоянно растущей (бесконечной) спирали, какую структуру данных хорошо поддерживать, и, возможно, идеи для вывода (графический файл, текстовый файл?).

Как бы вы поступили об этом?

Ответы [ 4 ]

8 голосов
/ 20 августа 2009

Рассмотрим длину каждой стороны: 1, 1, 2, 2, 3, 3, 4, 4, ...

Простая вещь - это перебирать каждую сторону, рендеринг этой стороны. Вы можете использовать примитивы рендеринга в стиле LOGO: 

Angle = 0;
x=0; y = 0;
int number = 1;
int sideLength = 1;

StartLine();
for (int side = 1; side < maxSize; side++) {
 for (int k = 0; k < sideLength; k++) {
  Forward(1);
  number++;

  if (isPrime(number)) {
   StopLine();
   Ouput(number);
   StartLine();
  }
 }
 TurnLeft();
 if (side % 2 == 0) sideLength++;
}

Вы можете улучшить это, перебирая простые числа на стороне:

5 голосов
/ 21 августа 2009

Следующая программа работает путем непосредственного вычисления координат числа. Метод NumberToPoint() выполняет следующее отображение. 

0 => (x0    , y0    )
1 => (x0 + 1, y0    )
2 => (x0 + 1, y0 - 1)
3 => (x0    , y0 - 1)
4 => (x0 - 1, y0 - 1)
5 => (x0 - 1, y0    )
6 => ...

Остальное - очень простой тест простых чисел и небольшое консольное приложение.

Чтобы сохранить изображение, я бы рассмотрел два решения. Если вы можете создать буфер для всего изображения, вы можете просто использовать программу ниже, чтобы заполнить буфер.

Если бы буфер был слишком большим, я бы создал метод PointToNumber() и инвертировал вычисление - метод берет две координаты и возвращает число в этой точке. С помощью этого метода вы можете выполнять итерацию сверху вниз и слева направо и вычислять число в этой точке, проверять, является ли оно простым, и выводить пиксель по ходу работы без буфера. Но для обоих решений размер изображения должен быть известен до того, как вы начнете, потому что добавление пикселей вверху и слева довольно дорого (но возможно по причине).

Вопросы

  1. Какие-нибудь хорошие идеи для преобразования коэффициента поиска в NumberToPoint() в твердую математику без использования модуля, целочисленного деления и знака тысячи раз?
  2. Какие-нибудь хорошие идеи по сокращению или ускорению теста простых чисел?

Код 

using System;
using System.Drawing;
using System.Linq;
using System.Threading;

namespace UlamsSpiral
{
   public static class Program
   {
      public static void Main()
      {
         Int32 width = 60;
         Int32 height = 60;

         Console.SetWindowSize(Math.Min(width, 120), Math.Min(height, 60));
         Console.SetBufferSize(width, height);
         Console.CursorVisible = false;

         Int32 limit = (Int32)Math.Pow(Math.Min(width, height) - 2, 2);

         for (Int32 n = 1; n <= limit; n++)
         {
            Point point = NumberToPoint(n - 1, width / 2 - 1, height / 2);

            Console.ForegroundColor = n.IsPrime() ? ConsoleColor.DarkBlue : ConsoleColor.DarkGray;

            Console.SetCursorPosition(point.X, point.Y);
            Console.Write('\u25A0');

            Console.SetCursorPosition(0, 0);
            Console.Write(n);

            Thread.Sleep(10);
         }

         Console.ReadLine();
      }

      private static Point NumberToPoint(Int32 n, Int32 x0, Int32 y0)
      {
         Int32[,] c = { { -1, 0, 0, -1, 1, 0 }, { -1, 1, 1, 1, 0, 0 }, { 1, 0, 1, 1, -1, -1 }, { 1, -1, 0, -1, 0, -1 } };

         Int32 square = (Int32)Math.Floor(Math.Sqrt(n / 4));

         Int32 index;
         Int32 side = (Int32)Math.DivRem(n - 4 * square * square, 2 * square + 1, out index);

         Int32 x = c[side, 0] * square + c[side, 1] * index + c[side, 2];
         Int32 y = c[side, 3] * square + c[side, 4] * index + c[side, 5];

         return new Point(x + x0, y + y0);
      }

      private static Boolean IsPrime(this Int32 n)
      {
         if (n < 3) return (n == 2);
         return Enumerable.Range(2, (Int32)Math.Sqrt(n)).All(m => n % m != 0);
      }
   }
}
0 голосов
/ 21 августа 2009

Почему бы не иметь процесс / поток "генератор", который создает числа, и процесс / поток "читатель / дисплей", который их отображает, тогда вы можете отделить создание от дисплея, и тогда программа будет действительно ограничена только сколько данных потребляет «читатель / дисплей». Поскольку я предполагаю, что «генератору» нужен набор данных довольно постоянного размера для работы.

0 голосов
/ 20 августа 2009

Один из возможных способов сделать это - создать линейный массив или список для хранения чисел и использовать формулу для определения необходимости изменения направления. Что касается вывода, мне понравился пример рисования черного пикселя для простого числа и белого пикселя для всех остальных чисел.

...