홍라이프 계산기소수 판별 쉽게 이해하기 — 개념과 원리
소수는 1보다 큰 자연수 가운데 1과 자기 자신만을 약수로 갖는 수입니다. 이 계산기는 입력한 수가 소수인지 판별하고, 소수가 아니면 소인수분해 결과를 보여 주며, 바로 위와 아래에 있는 소수도 찾아 줍니다. 수학 숙제와 퍼즐, 프로그래밍 연습, 증명에 쓸 수를 고를 때 확인용으로 유용합니다. 참고로 우리말에서 소수(素數)는 0.5 같은 소수(小數)와 한자가 다른 별개의 말입니다.
계산 방법
- 2보다 작은 수는 소수가 아니고, 2와 3은 소수입니다.
- 2나 3으로 나누어떨어지면 합성수입니다.
- 그 밖에는 6k − 1, 6k + 1 꼴의 수(5, 7, 11, 13, 17, 19…)로 √n 이하까지 나누어 봅니다. 하나도 나누어떨어지지 않으면 소수입니다.
- 다음 소수는 n + 1, n + 2…를, 이전 소수는 n − 1, n − 2…를 차례로 검사해 찾습니다.
원리
n에 √n보다 큰 약수가 있다면 그 짝이 되는 약수는 √n보다 작으므로, √n까지만 확인하면 충분합니다. 모든 정수는 6k, 6k ± 1, 6k + 2, 6k + 3, 6k + 4 중 하나로 쓸 수 있는데, 6k, 6k + 2, 6k + 4는 짝수이고 6k + 3은 3의 배수입니다. 따라서 2와 3을 뺀 모든 소수는 6k ± 1 꼴이며, 이를 이용하면 후보의 3분의 2를 건너뛸 수 있습니다. 유클리드가 소수는 무한히 많다는 것을 증명했으므로 다음 소수는 언제나 존재합니다.
예제 풀이
- 입력값: 97이고, √97 ≈ 9.85이므로 9 이하의 수만 확인하면 됩니다.
- 97은 홀수이고, 각 자리 숫자의 합 16이 3의 배수가 아닙니다.
- 9 이하의 6k ± 1 꼴 후보는 5와 7입니다. 97 ÷ 5 = 19.4, 97 ÷ 7 ≈ 13.86으로 나누어떨어지지 않습니다.
- 결과는 97은 소수입니다(yes, 97 is prime).
- 98, 99, 100은 합성수이고 101은 소수이므로 다음 소수는 101입니다.
- 96부터 90까지는 모두 합성수이고 89는 소수이므로 이전 소수는 89입니다.
결과 해석
소수가 아니면 소인수분해가 함께 표시되어 가장 작은 소인수를 바로 알 수 있습니다. 이웃한 두 소수의 차이를 소수 간격이라고 하는데, 89와 97 사이의 간격 8은 이 크기의 수로서는 큰 편입니다. 평균적으로 n 근처의 소수는 약 ln n 간격으로 나타나므로, 수가 커질수록 소수는 천천히 드물어집니다.
흔한 실수
- 1을 소수로 여깁니다. 소인수분해가 한 가지로 정해지도록 1은 소수에서 제외합니다.
- 홀수면 소수라고 생각합니다. 91 = 7 × 13이 대표적인 함정입니다.
- √n 대신 n/2까지 나누어 봅니다. 틀리지는 않지만 불필요하게 오래 걸립니다.
자주 묻는 질문
짝수인 소수는 2뿐인가요?
네. 2 이외의 짝수는 2로 나누어떨어지므로 약수가 적어도 세 개입니다.
100보다 작은 소수는 몇 개인가요?
2부터 97까지 25개이며, 97은 가장 큰 두 자리 소수입니다.
컴퓨터는 아주 큰 수가 소수인지 어떻게 판별하나요?
밀러-라빈 같은 확률적 판정법이나 AKS, 타원곡선을 이용한 판정법을 써서 나눗셈보다 훨씬 빠르게 확인합니다.
출처: Euclid, Elements, Book IX 명제 20(소수의 무한성) · G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Chapters 1–2 · M. Agrawal, N. Kayal and N. Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004)