울람의 나선(소수 나선)

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

나머지는 매우 간단한 소수 테스트와 작은 콘솔 응용 프로그램입니다.

이미지를 저장하기 위해 두 가지 솔루션을 고려할 것입니다. 전체 이미지에 대한 버퍼를 만들 수 있다면 아래 프로그램을 사용하여 버퍼를 채울 수 있습니다.

버퍼가 큰 경우 방법을 만들 것입니다. PointToNumber() 계산을 반전시 -이 방법은 두 개의 좌표를 가져 와서이 시점에서 숫자를 반환합니다. 이 메소드를 사용하면 위에서 왼쪽에서 왼쪽에서 오른쪽으로 반복 하고이 시점에서 숫자를 계산하고, 프라임인지 확인하고 버퍼없이 갈 때 픽셀을 출력 할 수 있습니다. 그러나 두 솔루션 모두 상단과 왼쪽에 픽셀을 추가하는 것이 상당히 비싸기 때문에 이미지 크기를 시작하기 전에 이미지 크기를 알아야합니다.

질문

  1. 계수 조회를 변환하기위한 좋은 아이디어 NumberToPoint() 정수 부서 인 Modulo를 사용하지 않고 견고한 수학으로 수천 번 서명합니까?
  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);
      }
   }
}

이를 수행하는 한 가지 방법 중 하나는 선형 배열 또는 목록을 작성하여 숫자를 저장하고 방향이 변경되어야하는시기를 결정하기 위해 공식을 사용하는 것입니다. 출력에 관해서는 Wikipedia의 예제가 프라임을위한 검은 색 픽셀과 다른 모든 숫자의 흰색 픽셀을 그리는 예를 좋아했습니다.

숫자를 생성하는 "생성기" 프로세스/스레드와 숫자를 표시하는 "리더/디스플레이" 프로세스/스레드를 사용하면 디스플레이에서 생성을 분리할 수 있으며 프로그램은 실제로 데이터 양에 의해서만 제한됩니다. "리더/디스플레이"가 소비합니다.나는 "생성기"가 작업하려면 상당히 일정한 크기의 데이터 세트가 필요하다고 가정하기 때문입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top