Espiral de Ulam (Prime Number Spiral)

Question

Estoy buscando ideas / código (preferiblemente C #, pero otros idiomas trabajar también) para crear de Ulam espiral infinitamente grande (limitado por la longitud de tiempo que el programa se está ejecutando, o hasta que se detuvo).

Ahora los números primos son todos lo que el código para los que es bastante irrelevante. La parte interesante es cómo codificar la disposición en la espiral siempre creciente (infinita), qué tipo de estructura de datos es bueno para apoyarlo, y tal vez ideas para la salida (archivo de gráficos, archivos de texto?).

¿Cómo hacerlo?

Answer 1

Considere las longitudes de cada lado:  1, 1, 2, 2, 3, 3, 4, 4, ...

Lo más sencillo es para iterar sobre cada lado, lo que hace ese lado. Puede utilizar el logotipo primitivas Estilo de reproducción:

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

Es posible mejorar esta sólo iterar sobre los números primos en un lado:

Answer 2

El siguiente programa funciona calculando directamente las coordenadas de un número. El NumberToPoint() método realiza el siguiente mapeo.

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 => ...

El resto es una prueba muy simple número primo y una pequeña aplicación de consola.

Con el fin de guardar una imagen que yo consideraría dos soluciones. Si usted puede crear un búfer para toda la imagen, sólo puede utilizar el programa siguiente para llenar el búfer.

Si la memoria intermedia sería grande, me gustaría crear un método PointToNumber() e invertir el cálculo - el método tiene dos coordenadas y devuelve el número en este punto. Con este método se puede recorrer de arriba a abajo y de izquierda a derecha y calcular el número en este punto, comprobar si es primo, y la salida del píxel a medida que avanza sin un búfer. Pero para ambas soluciones el tamaño de la imagen debe ser conocida antes de empezar, ya que la adición de píxeles en la parte superior izquierda y es bastante caro (pero de causa posible).

Preguntas

1. ¿Buenas ideas para convertir el coeficiente de operaciones de búsqueda en NumberToPoint() en la roca sólida de matemáticas sin usar módulo, la división entera, y firmar un millar de veces?
2. ¿Buenas ideas para acortar o aceleran la prueba número primo?

Código

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

Una posible forma de hacerlo es crear una matriz lineal o una lista para almacenar los números y el uso de una fórmula para determinar cuando la dirección tiene que cambiar. En cuanto a la salida, me ha gustado el ejemplo en la wikipedia de dibujar un píxel negro por un primer y un píxel blanco para todos los otros números.

Answer 4

¿Por qué no tener un "generador" proceso / hilo que crea los números y un "lector / pantalla" proceso / hilo que los muestra, entonces se puede separar la creación de la pantalla y luego el programa en realidad sólo estará limitada por la cantidad de datos del "lector / pantalla" consume. Dado que asumiría el "generador" necesita un conjunto de tamaño bastante constante de datos para trabajar con ellos.