Спираль Улама (спираль простых чисел)

Question

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

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

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

Answer 1

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

Самое простое — перебирать каждую сторону, визуализируя эту сторону.Вы можете использовать примитивы рендеринга в стиле ЛОГОТИПА:

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++;
}

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

Answer 2

Следующая программа работает путем прямого вычисления координат числа.Метод 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);
      }
   }
}

Answer 3

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

Answer 4

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