소수 판별기

정수가 소수(1과 자기 자신으로만 나누어지는 수)인지 확인하고, 소수가 아니라면 계산 한도 안에서 찾을 수 있는 소인수를 보여 줍니다. 3,317,044,064,679,887,385,961,981 미만의 수는 결정적 밀러–라빈 판정으로 처리하므로 소수 여부는 확률이 아니라 정확한 답입니다. 입력한 수 바로 앞뒤의 소수도 알려 줍니다.

사용 방법

1. 정수를 입력합니다. 쉼표와 공백은 무시합니다.
2. 소수, 합성수, 또는 둘 다 아님(0과 1)인지 확인합니다.
3. 합성수라면 소인수분해, 가장 작은 소인수, 약수의 개수를 확인합니다.
4. 이전 소수와 다음 소수로 가장 가까운 소수를 찾습니다.

계산식

n is prime ⇔ n > 1 and no prime p ≤ √n divides n

√n까지 나누어 보는 시행 나눗셈이 교과서적인 방법입니다. 큰 n에는 2부터 41까지의 소수 13개를 밑으로 하는 밀러–라빈 판정을 사용하며, 3.3 × 10²⁴ 미만에서는 오답이 없음이 증명되어 있습니다. 합성수는 시행 나눗셈과 폴라드 로 방법으로 분해합니다. 약수의 개수는 소인수분해에서 나옵니다. n = p₁^a × p₂^b × …이면 약수는 (a + 1)(b + 1)…개입니다.

예시

91: √91 ≈ 9.5이므로 2, 3, 5, 7만 확인하면 됩니다. 91 ÷ 7 = 13이므로 91은 합성수이고 91 = 7 × 13, 약수는 4개입니다. 97: 2, 3, 5, 7 중 어느 것으로도 나누어지지 않으므로 97은 소수이며, 이웃한 소수는 89와 101입니다. 360 = 2³ × 3² × 5이고 약수는 (3 + 1)(2 + 1)(1 + 1) = 24개입니다.