乌拉姆螺旋（质数螺旋）

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

  •  19-09-2019
  •  | 
  •  

题

我正在寻找想法/代码（最好是 C#，但其他语言也可以）来创建 乌拉姆的螺旋 无限大（受程序运行时间长度限制，或直到停止为止）。

alt text

现在数字都是素数，所以这些代码是相当无关紧要的。有趣的部分是如何对不断增长（无限）螺旋中的排列进行编码，什么样的数据结构可以很好地支持它，以及输出的想法（图形文件，文本文件？）。

你会怎么做呢？

有帮助吗？

解决方案

考虑每一侧的长度：  1，1，2，2，3，3，4，4，...

在简单的事情是遍历每一侧，使该侧。 您可以使用LOGO风格的渲染图元：

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

剩下的就是一个非常简单的素数测试和一个小型控制台应用程序。

为了保存图像我会考虑两种解决方案。如果您可以为整个图像创建一个缓冲区，则可以使用下面的程序来填充缓冲区。

如果缓冲区太大，我会创建一个方法 PointToNumber() 并反转计算 - 该方法采用两个坐标并返回此时的数字。使用此方法，您可以从上到下、从左到右迭代并计算此时的数字，检查它是否为素数，然后在没有缓冲区的情况下输出像素。但对于这两种解决方案，在开始之前都应该知道图像大小，因为在顶部和左侧添加像素非常昂贵（但有可能）。

问题

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

一种可能的方式来做到这一点是创建一个线性阵列或存储的数字，并使用公式来确定当方向需要改变列表。 至于输出，我喜欢的例子上绘制黑色像素要素和白像素的所有其它号码的维基百科。

为什么不能有一个“发电机”进程/线程创建的数量和“读取器/显示”进程/线程，显示它们，那么你可以与显示器分离的创建和程序将只真的被限制多少数据“读/显示器”消耗。因为我将承担“发电机”需要一个相当恒定大小的数据集的工作。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top