정수가 소수인지 확인하고, 소수가 아니면 가장 작은 약수를 알려 줍니다.
계산은 기기에서 처리되며 입력값을 서버로 보내지 않습니다.
97은 소수이고, 1,000번째 소수인 7,919도 소수입니다. 91은 91 = 7 × 13이라 소수가 아니며, 221도 221 = 13 × 17이므로 13으로 나누어떨어집니다.
먼저 2와 짝수를 처리한 뒤, 입력한 수의 제곱근까지 홀수 약수만 시험합니다. 제곱근보다 큰 약수가 있다면 짝이 되는 수가 더 작아 이미 발견되었을 것이기 때문입니다. 10억 미만에서 가장 큰 소수인 999,999,937도 시험 나눗셈이 최대 약 15,800회면 충분해서 결과가 거의 바로 나옵니다.
2부터 1,000,000,000까지의 정수를 입력하세요. 소수는 양의 약수가 정확히 두 개인 수이므로 1은 소수가 아닙니다. 소수 여부는 정수에 대한 성질이라 소수점이 있는 수는 받지 않습니다. 합성수라면 1보다 큰 가장 작은 약수를 함께 보여 줍니다.
2부터 1,000,000,000까지의 정수를 입력하세요. 소수는 약수가 정확히 두 개이며 97과 7,919는 소수입니다. 소수가 아니면 1보다 큰 가장 작은 약수를 보여 줍니다(91 = 7 × 13). 1은 소수가 아니고 2는 유일한 짝수 소수입니다. 제곱근까지의 홀수로만 나눠 보는데, 더 큰 인수에는 반드시 더 작은 짝이 있기 때문입니다. 그래서 999,999,937도 즉시 판정됩니다. 561은 소수처럼 보이지만 3으로 나누어떨어집니다(5 + 6 + 1 = 12).
| 입력 | 결과 |
|---|---|
97 | ✓ |
7919 | ✓ |
999999937 | ✓ |
91 | ÷ 7 |
221 | ÷ 13 |
561 | ÷ 3 |
작은 약수는 쉽게 숨기 때문입니다. 561은 가장 작은 카마이클 수로 빠른 확률적 판정을 통과하기도 하지만 3으로 나누어떨어집니다. 각 자리 숫자를 더하면 드러납니다. 5 + 6 + 1 = 12는 3의 배수입니다. 이 도구는 실제로 나눠 보므로 답이 정확합니다.
약수는 짝을 이루기 때문입니다. 221은 13에 도달하는 순간 검사가 끝납니다. 221 = 13 × 17이고, 이보다 큰 약수는 이미 더 작은 짝과 함께 확인되었을 것이기 때문입니다. 덕분에 10억에 가까운 수도 빠르게 판정할 수 있습니다.
아니요. 이 도구는 학습과 일상적인 확인을 위해 1,000,000,000까지를 다룹니다. 암호에 쓰이는 소수는 수백 자리이며 확률적 판정법과 안전한 난수로 생성합니다. 시험 나눗셈으로는 현실적인 시간 안에 처리할 수 없습니다.