Ulamのスパイラル（素数スパイラル）

Question

Ulam's Spiral（プログラムが実行されている時間または停止するまでの時間によって制限される）を作成するためのアイデア/コード（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

可能な方法の1つは、線形配列または数値を格納するListを作成し、式を使用して方向を変更する必要があるかどうかを判断することです。 出力に関しては、ウィキペディアの例では、他のすべての数字の場合は、素数ピクセルと黒ピクセルの黒ピクセルを描画するのが好きでした。

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

残りは、非常に単純な素数テストと小さなコンソールアプリケーションです。

イメージを保存するために、私は2つのソリューションを検討します。イメージ全体のバッファを作成できる場合は、以下のプログラムを使用してバッファを満たすことができます。

バッファーが大きい場合は、メソッドPointToNumber()を作成し、計算を逆転させます。メソッドは2つの座標を取り、この時点で番号を返します。このメソッドを使用すると、上から下、左から右への繰り返しができ、この時点での数を計算し、素数かどうかをチェックし、バッファなしで出力することができます。しかし、上と左のピクセルを追加するのはかなりコストがかかるので（しかし、可能な限り）、両方のソリューションでイメージのサイズを確認する必要があります。

質問

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

番号とそれらを表示する「リーダ/表示」プロセス/スレッドを作成し、「発電機」のプロセス/スレッドを持っていないのはなぜ、あなたが作成を分離することができますそして、プログラムは、「リーダ/ディスプレイ」がどれだけのデータを消費するかによって実際には制限されます。私は、 "ジェネレータ"にはかなり一定のサイズのデータ​​セットが必要であると想定しています。