Ulam의 나선형 (소수 번호 나선형)

Ulam's Spiral (프로그램이 실행되는 시간 또는 중지 될 때까지의 시간으로 제한됨)을 만들기 위해 아이디어/코드 (C#,하지만 다른 언어도 가능)를 찾고 있습니다. 이들에 대한 코드는 다소 무관하므로Ulam의 나선형 (소수 번호 나선형)

이제 숫자는 모두 소수이다. 흥미로운 부분은 끊임없이 늘어나는 (무한한) 나선형의 배열을 코딩하는 방법, 어떤 종류의 데이터 구조를 지원하는 것이 좋을지, 그리고 아마도 출력을위한 아이디어 (그래픽 파일, 텍스트 파일)입니다.

어떻게 하시겠습니까?

출처

2009-08-20 Alex

각 변의 길이를 고려 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++; 
}

을 :

출처

2009-08-20 19:48:40 Justin

+1 로고를 참조하는 경우 - 좋은 접근 방식입니다! – Nelson

선형 배열 또는 숫자를 저장하는 List를 만들고 수식을 사용하여 방향을 변경해야 할 때를 결정할 수 있습니다. 출력에 관해서는 위키피디아에서 다른 모든 숫자의 소수 픽셀과 흰색 픽셀을 그리는 예제가 마음에 들었습니다.

출처

2009-08-20 19:23:51 murgatroid99

다음 프로그램은 직접 숫자의 좌표를 계산하여 작동합니다. 방법 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() 메서드를 만들고 계산을 반전합니다.이 메서드는 두 좌표를 사용하고이 지점에서 숫자를 반환합니다. 이 방법을 사용하면 위에서 아래로, 왼쪽에서 오른쪽으로 반복하고이 시점에서 수를 계산하고 소수인지 확인하고 버퍼없이 진행하면서 픽셀을 출력 할 수 있습니다. 하지만 두 솔루션 모두 이미지 크기는 시작하기 전에 알아야합니다. 상단 및 왼쪽에 픽셀을 추가하는 것은 비용이 많이 듭니다 (하지만 가능할 수도 있기 때문).

질문

모듈, 정수 나누기를 사용하지 않고 견고한 수학에 NumberToPoint()에서 계수 조회 변환에 대한 모든 좋은 아이디어, 서명 천 번?
소수 테스트를 단축하거나 빠르게하는 데 유용한 아이디어가 있습니까?

코드

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

출처

2009-08-20 22:15:37

숫자와이를 표시하는 "리더/디스플레이"프로세스/쓰레드를 생성하는 "발전기"프로세스/스레드를하지 왜, 당신은 생성을 분리 할 수 있습니다 프로그램에서 실제로 "리더/디스플레이"가 소비하는 데이터의 양에 따라 제한 될 것입니다. 이후 나는 "발전기"와 함께 작동하도록 상당히 일정한 크기의 데이터 세트가 필요하다고 가정합니다.

출처

2009-08-20 22:49:55

Ulam의 나선형 (소수 번호 나선형)

답변

관련 문제