소수란 무엇인가요?
소수는 1보다 큰 자연수 중에서 양의 약수가 1과 자기 자신, 이렇게 딱 두 개만 있는 수입니다. 반대로 약수가 세 개 이상인 수는 합성수라고 부릅니다. 숫자 1은 좀 특별한데, 약수가 1 하나뿐이라서 소수도 합성수도 아닙니다. 이 계산기는 입력한 수가 소수인지 합성수인지 판별하고, 약수를 모두 나열하며, 바로 앞과 뒤에 오는 소수까지 함께 보여 줍니다.
사용 방법
1보다 큰 정수를 입력하고 실행 버튼을 누르기만 하면 됩니다. 입력한 수가 소수인지 합성수인지 분류해 주고, 그 수를 다시 한번 표시한 뒤, (합성수라면) 모든 약수를 보여 줍니다. 또한 그 수보다 작은 가장 큰 소수와 그 수보다 큰 가장 작은 소수도 알려 줍니다.
계산 원리
이 계산기는 6k±1 최적화를 적용한 결정적 시산법(trial division)을 사용합니다. 먼저 2와 3은 이미 알려진 소수이므로 따로 처리하고, 짝수와 3의 배수는 곧바로 걸러냅니다. 그다음에는 6k-1, 6k+1 형태의 후보 약수(5, 7, 11, 13, ...)만 n의 제곱근까지 나눠 봅니다. 이 중 어느 것으로도 n이 나누어떨어지지 않으면 n은 소수입니다. 제곱근까지만 확인하면 되는 이유는, 제곱근보다 큰 약수는 반드시 제곱근보다 작은 약수와 짝을 이루기 때문입니다.
$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$
예제로 살펴보기
\(n = 97\)을 예로 들어 보겠습니다. 97의 제곱근은 약 9.85입니다. 97은 홀수이고 3의 배수도 아닙니다. 그래서 5로 나눠 보면(\(97 \bmod 5 = 2\)), 7로 나눠 봅니다(\(97 \bmod 7 = 6\)). 다음 후보는 11인데, \(11 \times 11 = 121 > 97\)이므로 여기서 멈춥니다. 어떤 약수도 찾지 못했으니 97은 소수입니다. 바로 앞 소수는 89, 바로 뒤 소수는 101입니다.
자주 묻는 질문
1은 소수인가요? 아닙니다. 1은 약수가 하나뿐이라서 소수도 합성수도 아닙니다.
2는 소수인가요? 네, 맞습니다. 2는 가장 작은 소수이자 유일한 짝수 소수입니다. 2 앞에는 소수가 없습니다.
약수는 왜 합성수일 때만 나열하나요? 소수는 정의상 약수가 1과 자기 자신뿐이라서 그 사실만 알려 주면 충분합니다. 반면 합성수는 약수가 여러 개일 수 있어, 작은 순서대로 모두 나열합니다.
