Espiral de Ulam (Prime Number Spiral)
Pergunta
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?
Solução
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:
Outras dicas
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
- 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? - 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);
}
}
}
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.
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.