Espiral de Ulam (Prime Number Spiral)

Question

Eu estou procurando idéias / code (preferencialmente C #, mas outras línguas trabalhar também) para criar Ulam de espiral infinitamente grande (limitado pelo comprimento de tempo que o programa está em execução, ou até que seja parado).

Agora, os números são todos números primos para que o código para aqueles é bastante irrelevante. A parte interessante é como código o arranjo na espiral sempre crescente (infinito), que tipo de estrutura de dados é bom para apoiá-lo, e talvez ideias para a saída (arquivo gráfico, arquivo de texto?).

Como você iria sobre isso?

Answer 1

Considere os comprimentos de cada lado: 1, 1, 2, 2, 3, 3, 4, 4, ...

A coisa simples é para iterar sobre cada lado, tornando esse lado. Você pode usar o logotipo primitivas de processamento estilo:

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

Você pode melhorar esta apenas por iteração sobre números primos em um lado:

Answer 2

O seguinte programa funciona por meio do cálculo diretamente as coordenadas de um número. Os executa método NumberToPoint() o seguinte mapeamento.

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

O resto é muito simples teste de número primo e um pequeno aplicativo de console.

A fim de salvar uma imagem que eu iria considerar duas soluções. Se você pode criar um buffer para a imagem inteira, você pode simplesmente usar o programa abaixo para preencher o buffer.

Se o buffer seria grande, eu criaria um PointToNumber() método e invertido o cálculo - o método leva duas coordenadas e retorna o número neste momento. Com este método você pode interagir de cima para baixo e da esquerda para a direita e calcular o número neste momento, verifique se ele é primo, e a saída do pixel como você ir sem um buffer. Mas para ambas as soluções do tamanho da imagem deve ser ser conhecidos antes de começar, porque a adição de pixels na parte superior e esquerda é muito caro (mas de causa possível).

Perguntas

1. Alguma boa idéia para converter a pesquisa coeficiente NumberToPoint() na rocha matemática sólida sem o uso de modulo, integer divisão, e assinar mil vezes?
2. Alguma boa idéia para diminuir ou acelerar o teste número primo?

Código

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

Uma forma possível de fazer isso é criar uma matriz linear ou uma lista para armazenar os números e usar uma fórmula para determinar quando as necessidades direção à mudança. Quanto à saída, eu gostei do exemplo na wikipedia de desenhar um pixel preto para um um pixel branco nobre e para todos os outros números.

Answer 4

Por que não ter um "gerador" processo / thread que cria os números e um processo / thread "leitor / display" que exibe, em seguida, você pode separar a criação do visor e, em seguida, o programa só vai realmente ser limitados por a quantidade de dados o "leitor / exibição" consome. Desde que eu assumiria o "gerador" precisa de um conjunto de tamanho razoavelmente constante de dados para trabalhar com ele.