이 계산기로 할 수 있는 일
이 도구는 입력한 정수가 소수인지 합성수인지 알려줍니다. 1보다 큰 소수는 약수가 정확히 두 개, 즉 1과 자기 자신뿐입니다. 합성수는 그 외에 적어도 하나 이상의 약수를 더 가집니다. 0과 1은 소수도 합성수도 아니므로, 이 계산기는 2 이상의 수를 입력받습니다.
사용 방법
입력란에 원하는 정수를 적고 실행하면 됩니다. 계산기는 그 수가 소수인지 합성수인지 분류해 알려주며, 합성수일 경우에는 가장 작은 소인수와 인수분해 예시(가장 작은 약수 \(\times\) 그에 대응하는 약수)까지 함께 보여줍니다.
원리(공식) 설명
판별에는 시험 나눗셈(trial division)을 사용합니다. n이 합성수인지 확인하려면 2부터 n의 제곱근까지의 약수 d만 검사하면 됩니다. 이 범위에서 n을 나누어떨어지게 하는 d가 하나라도 있으면 n은 합성수이고, 하나도 없으면 소수입니다. \(\sqrt{n}\)까지만 검사해도 충분한 이유는, \(n = a \times b\)일 때 두 인수 중 적어도 하나는 반드시 \(\sqrt{n}\) 이하이기 때문입니다.
$$\text{Prime if } n > 1 \text{ and } \nexists\, d \in [2, \lfloor\sqrt{n}\rfloor] : n \bmod d = 0$$$$\text{Classify}(n) = \begin{cases} \text{Prime} & \nexists\, d \in [2,\lfloor\sqrt{n}\rfloor],\; n \bmod d = 0 \\[0.4em] \text{Composite} & \exists\, d \in [2,\lfloor\sqrt{n}\rfloor],\; n \bmod d = 0 \\[0.4em] \text{Neither} & n < 2 \end{cases}$$
예제 풀이
\(n = 91\)을 봅시다. 91의 제곱근은 약 9.54이므로 2, 3, 5, 7, 9를 검사합니다. \(91 \div 7 = 13\)으로 딱 나누어떨어지므로, 91은 가장 작은 소인수가 7이고 인수분해가 \(7 \times 13\)인 합성수입니다. 반면 97은 9까지 어떤 수로도 나누어떨어지지 않으므로 소수입니다.
자주 묻는 질문
1은 소수인가요? 아닙니다. 정의상 소수는 서로 다른 양의 약수를 정확히 두 개 가져야 하는데, 1은 약수가 하나뿐입니다.
2는 소수인가요? 네. 2는 유일한 짝수 소수입니다.
왜 제곱근까지만 검사하나요? \(\sqrt{n}\)보다 큰 약수는 항상 \(\sqrt{n}\)보다 작은 약수와 짝을 이루는데, 그 작은 약수는 이미 검사 범위에 포함됩니다. 따라서 \(\sqrt{n}\)을 넘어 검사하는 것은 불필요한 중복입니다.
