Ulams Spiral (Prime Number Spiral)

Question

Ich bin auf der Suche nach Ideen / Code (vorzugsweise C #, aber auch andere Sprachen arbeiten auch) erstellen Ulams Spiral unendlich groß (begrenzt durch lange das Programm ausgeführt wird, oder bis zum Stillstand).

Jetzt sind die Zahlen alle Primzahlen so dass der Code für die eher irrelevant ist. Der interessante Teil ist, wie die Anordnung codieren, in der stetig wachsenden (unendlich) Spirale, welche Art von Datenstruktur ist gut, sie zu unterstützen, und vielleicht Ideen für die Ausgabe (Grafikdatei, Textdatei?).

Wie würden Sie vorgehen?

Answer 1

Beachten Sie die Längen von jeder Seite:  1, 1, 2, 2, 3, 3, 4, 4, ...

Die einfache Sache ist, über jede Seite zu durchlaufen, die Seite zu machen. Sie können LOGO-Wiedergabe Primitive verwenden:

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

Sie können dies verbessern, indem sie nur über Primzahlen auf einer Seite Iterieren:

Answer 2

Das folgende Programm funktioniert, indem direkt die Koordinaten einer Zahl zu berechnen. Das Verfahren NumberToPoint() führt die folgende Abbildung.

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

Der Rest ist ein sehr einfacher Primzahl Test und eine kleine Konsolenanwendung.

Um ein Bild zu speichern, würde ich zwei Lösungen in Betracht ziehen. Wenn Sie einen Puffer für das gesamte Bild erstellen können, können Sie einfach mit dem Programm unter den Puffer zu füllen.

Wenn der Puffer zu groß wäre, würde ich eine Methode PointToNumber() schaffen und die Berechnung umkehren - das Verfahren dauert zwei Koordinaten und gibt die Anzahl an dieser Stelle. Mit dieser Methode können Sie von oben nach unten durchlaufen und links die Anzahl an dieser Stelle nach rechts und zu berechnen, ob es eine Primzahl ist und die Ausgabe des Pixels, wie Sie ohne einen Puffer gehen. Aber für beiden Lösungen soll die Bildgröße bekannt sein, bevor Sie beginnen, weil das Hinzufügen von Pixeln an der Spitze und links recht teuer ist (aber Ursache möglich).

Fragen

1. Jede gute Ideen für den Koeffizienten-Lookup in NumberToPoint() in rock solid Mathematik Umwandlung ohne Verwendung von Modulo, Integer-Division, und tausendmal schreiben?
2. Jede gute Ideen zu verkürzen oder die Primzahl Test zu beschleunigen?

Code

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

Eine Möglichkeit, es zu tun, ist eine lineare Anordnung oder eine Liste zu erstellen, um die Zahlen zu speichern und eine Formel verwenden, um zu bestimmen, wenn die Richtung ändern muss. Wie für die Ausgabe, ich mochte das Beispiel auf wikipedia einen schwarzen Pixel für eine Primzahl und ein weißes Pixel für alle andere Zahlen zu ziehen.

Answer 4

Warum nicht einen „Generator“ Prozess / Thread hat, die die Zahlen und einen „Leser / Anzeige“ Prozess / Thread, den sie zeigt schaffen, dann können Sie die Erstellung von Display trennen und dann wird das Programm wirklich nur begrenzt durch wie viele Daten der „Leser / Display“ verbraucht. Da ich der „Generator“ mit einer relativ konstanten Größe Menge von Daten benötigt würde davon ausgehen, zu arbeiten.