Ulam a Spirale (Numero Primo Spirale)

Question

Sto cercando idee/codice (preferibilmente C#, ma in altre lingue di lavoro troppo) per creare A Spirale di Ulam infinitamente grande (limitato dalla lunghezza del tempo che il programma è in esecuzione, o fino a quando viene arrestato).

Ora i numeri sono tutti i numeri primi in modo che il codice per chi è piuttosto irrilevante.La parte interessante è come codice la composizione in crescente (infinito) a spirale, che tipo di struttura dati è buona per il supporto, e forse idee per l'output (file di immagini, file di testo?).

Come pensate di fare per questo?

Answer 1

Considerate le lunghezze di ogni lato:  1, 1, 2, 2, 3, 3, 4, 4, ...

La cosa semplice è quello di iterare su ogni lato, rendendo quel lato. È possibile utilizzare il logo primitive Stile di rendering:

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

Si potrebbe migliorare questo da solo l'iterazione di numeri primi su un lato:

Answer 2

Il seguente programma funziona calcolando direttamente le coordinate di un numero. Il metodo NumberToPoint() esegue la seguente mappatura.

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

Il resto è un test molto semplice numero primo e di una piccola applicazione console.

Al fine di salvare un'immagine vorrei prendere in considerazione due soluzioni. Se si riesce a creare un buffer per l'intera immagine, si può semplicemente utilizzare il programma qui sotto per riempire il buffer.

Se il buffer sarebbe di grande, che creerebbe un metodo PointToNumber() e capovolgere il calcolo - il metodo richiede due coordinate e restituisce il numero a questo punto. Con questo metodo è possibile scorrere dall'alto verso il basso e da sinistra a destra e calcolare il numero, a questo punto, verificare se è primo, e l'uscita del pixel come si va senza un buffer. Ma per entrambe le soluzioni la dimensione dell'immagine deve essere essere noto prima di iniziare, perché l'aggiunta di pixel nella parte superiore e sinistra è piuttosto costoso (ma di causa possibile).

Domande

1. Tutte le buone idee per convertire la ricerca coefficiente NumberToPoint() nella roccia solida di matematica senza l'utilizzo di modulo, divisione intera, e firmare un migliaio di volte?
2. Tutte le buone idee di ridurre o accelerare il test numero primo?

Codice

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

Un possibile modo per farlo è creare un array lineare o un elenco per memorizzare i numeri e utilizzare una formula per determinare quando la direzione deve cambiare. Per quanto riguarda l'uscita, mi piaceva l'esempio su wikipedia di disegnare un pixel nero per un primo e un pixel bianco per tutti gli altri numeri.

Answer 4

Perché non avere un "generatore" di processo/thread che crea i numeri e un "lettore/display" processo/thread che li visualizza, quindi è possibile separare la creazione del display e poi il programma sarà veramente solo essere limitata dalla quantità di dati che il "lettore/display" consuma.Dal momento che vorrei assumere il "generatore" ha bisogno di una abbastanza costante di dimensioni set di dati da utilizzare.