소수 판별 & 소인수분해

소수인지 아닌지, 그 근거까지

정수를 입력하면 소수인지 아닌지를 한 문장으로 알려 주고, 소수가 아니면 그 근거를 바로 아래에 보여 줍니다 — 60은 소수가 아니며, 60 = 2² × 3 × 5. 그 아래에는 그 수가 무엇으로 나누어지는지(약수)와 앞뒤로 가장 가까운 소수가 나옵니다. 페이지가 알려 주는 크기까지는 그 수 이하 소수의 개수 π(n)도 나오고, "풀이 보기"를 펼치면 나눗셈 과정이 — 소수라면 제곱근까지 나눠 본 소수들이 — 나옵니다. 약수 목록은 “소수가 아니다”라는 답을 믿을 수 있게 만들어 주는 부분입니다. 별도 섹션에서는 두 수 사이의 모든 소수를 나열할 수 있습니다. 소수는 2 이상이면서 1과 자기 자신 외에는 약수가 없는 수이며, 0·1·음수·소수점 값은 소수가 아니고 소인수분해도 정의되지 않습니다.

어디까지, 얼마나 빠르게

제곱근까지만 나눠 보는 시행 나눗셈을 쓰되 6k ± 1 꼴이 아닌 수는 건너뛰므로, 1조 정도까지는 즉시 결과가 나오고 자바스크립트가 정확히 다룰 수 있는 가장 큰 정수인 9,007,199,254,740,991까지도 (즉시는 아니어도) 계산됩니다. 그보다 큰 수도 숫자로만 적으면 정확한 큰 정수로 읽어 밀러–라빈 판정법으로 확인합니다. 페이지가 알려 주는 경계 아래에서는 증명이고, 그 위에서는 “거의 확실히 소수”라고 답합니다. 약수 목록은 약수가 200개 이하인 수에만 나타납니다 — 그보다 긴 목록은 화면에서 쓸모도 없고 만드는 비용도 크기 때문입니다 — 화면에는 앞의 24개와 나머지 개수가 표시됩니다. 범위 섹션은 수가 최대 100만 개인 구간까지 다룹니다. 개수는 구간 안의 소수를 모두 센 값이고, 목록에는 앞쪽 500개를 복사할 수 있게 보여 주며, "쌍둥이 소수 표시"를 켜면 p와 p + 2 쌍을 표시합니다. “이웃한 소수 사이의 간격 보기”는 목록의 각 소수에서 다음 소수까지의 간격과 가장 큰 간격을 보여 줍니다. 마지막 섹션 “더해서 짝수가 되는 두 소수”는 짝수를 두 소수의 합으로 나누되 앞의 소수가 가장 작은 분할을 고릅니다 — 골드바흐 추측은 4 이상의 모든 짝수에 이런 분할이 있다고 말합니다. 증명되지는 않았지만 이 칸에 넣을 수 있는 수보다 훨씬 큰 수까지 확인되었습니다.

소인수분해가 중요한 이유

소인수분해는 정수론의 기초로, 분수 약분과 최소공배수 계산부터 암호화 키의 원리까지 폭넓게 쓰입니다. 1보다 큰 모든 정수는 소인수분해가 유일하게 결정되므로, 여기서 보는 분해 결과는 그 수에 대한 단 하나의 정답입니다. 모든 계산은 브라우저 안에서 이뤄지므로 원하는 만큼 제한 없이 확인할 수 있습니다.