다음 소수 계산기

정수를 입력하면 그보다 큰 가장 작은 소수, 그보다 작은 가장 큰 소수, 둘 사이의 간격, 그리고 이어지는 소수 10개를 알려 줍니다. 10^24까지의 수를 지원하며 정확한 정수 연산을 쓰므로 1조나 10^18 다음의 첫 소수도 찾을 수 있습니다.

사용 방법

1. 숫자를 입력합니다. 쉼표, 1e12, 10^12 모두 괜찮습니다.
2. 입력한 수가 소수일 때 그 수 자체를 답으로 하려면 확인란을 선택합니다.
3. 다음 소수, 이전 소수, 간격을 확인합니다.
4. 표에서 이어지는 소수 10개와 그 사이의 간격을 살펴봅니다.

계산식

다음 소수(n) = p > n 이면서 소수인 가장 작은 p

n + 1, n + 2, …를 차례로 검사합니다. 각 후보는 먼저 1,000 미만의 소수로 나누어 보고, 통과한 수는 13개의 소수 밑 2, 3, 5, …, 41을 쓰는 밀러–라빈 판정을 거칩니다. 이 밑의 집합은 3.3 × 10^24 미만의 모든 수에서 오판이 없음이 증명되어 있으므로, 모든 답은 소수일 가능성이 아니라 확실한 소수입니다. 베르트랑 공준에 따라 1보다 큰 모든 n에 대해 n과 2n 사이에 소수가 있습니다.

예시

1,000,000 다음 소수는 1,000,003입니다. 1,000,001 = 101 × 9,901이고 1,000,002는 짝수이기 때문입니다. 이전 소수는 999,983이고, 입력한 수에서 다음 소수까지의 간격은 3입니다. 1,000,000,000 다음 소수는 프로그래머가 자주 쓰는 나눗셈 기준값 1,000,000,007입니다.