Спираль Улама (Prime Number Spiral)

Question

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

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

Как бы вы это сделали?

Answer 1

Рассмотрим длину каждой стороны: 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++; 
} 

Вы могли бы улучшить это лишь итерацию простых чисел на стороне:

Answer 2

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

Answer 3

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

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