이전 소수 계산기

이 도구는 이전 소수, 즉 입력한 수보다 작은 가장 큰 소수를 찾아 줍니다. 해시 테이블 크기를 정하거나, 소수 간격 숙제를 확인하거나, 2의 거듭제곱이나 10의 거듭제곱 바로 아래의 소수를 법으로 고를 때 편리합니다. 24자리까지의 정수를 정확하게 처리하며, 입력한 수 바로 아래의 소수 10개도 보여 줍니다.

사용 방법

1. 2보다 큰 정수를 입력합니다. 쉼표를 써도 되므로 1,000,000도 됩니다.
2. 이전 소수와 입력한 수보다 얼마나 작은지를 확인합니다.
3. 입력한 수 자체가 소수인지 확인합니다.
4. 표에서 그 아래의 소수들도 살펴봅니다.

계산식

prevprime(n) = max { p 는 소수 : p < n }

n − 1부터 짝수를 건너뛰며 내려가면서 각 후보를 검사합니다. 후보가 밑 2, 3, 5, …, 41에 대한 밀러–라빈 검사를 통과하면 소수입니다. 이 13개의 밑을 쓰면 약 3.3 × 10²⁴ 미만의 모든 수에서 오판이 없으므로, 답은 확률적이지 않고 확실합니다.

예시

n = 1,000,000이면 999,999(3으로 나누어떨어짐), 999,997(= 757 × 1,321)을 차례로 검사하며 내려가다가 처음 만나는 소수 999,983에서 멈춥니다. 간격은 1,000,000 − 999,983 = 17입니다. 그 아래의 소수는 999,979와 999,961입니다.