ウラムの螺旋 (素数螺旋)

StackOverflow https://stackoverflow.com/questions/1308039

  •  19-09-2019
  •  | 
  •  

質問

作成するアイデア/コード (できれば C# ですが、他の言語でも可能です) を探しています。 ウラムの螺旋 無限に大きくなります (プログラムの実行時間、または停止するまでの時間によって制限されます)。

alt text

数値はすべて素数なので、それらのコードはあまり意味がありません。興味深い部分は、成長し続ける (無限の) スパイラルの配置をどのようにコード化するか、それをサポートするにはどのようなデータ構造が適しているか、そしておそらく出力 (グラフィック ファイル、テキスト ファイル?) のアイデアです。

これについてはどうしますか?

役に立ちましたか？

解決

各辺の長さを考慮してください。  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++;
}

あなただけの側に素数を反復処理することによって、これを向上することがあります

他のヒント

次のプログラムは、数値の座標を直接計算することによって機能します。方法 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);
      }
   }
}

それを行うための1つの可能な方法は、リニアアレイまたは数値を格納し、方向を変更する必要がある場合を決定するために式を使用するためのリストを作成することです。 出力用として、私はすべての他の数のためにプライム及び白画素について黒画素を描画するのウィキペディアに例を言っています。

の番号とそれらを表示する「リーダ/表示」プロセス/スレッドを作成し、「発電機」のプロセス/スレッドを持っていないのはなぜ、あなたはディスプレイから作成を分離することができ、その後、プログラムはだけは本当にによって制限されますどのくらいのデータ「リーダー/ディスプレイ」を消費します。私は「発電機」はで動作するようにデータのほぼ一定の大きさのセットを必要とすると仮定しますので。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top