소수 판별 계산기

계산 입력

정수를 입력하세요

결과

Is 97 prime?

YES

This is a prime number

검사한 숫자	97
Result	Prime

소수란 무엇일까요?

소수(素數)는 1보다 큰 정수 중에서 1과 자기 자신, 이렇게 정확히 두 개의 양의 약수만 가지는 수를 말합니다. 2, 3, 5, 7, 11, 13 등이 대표적인 예입니다. 1보다 크면서 소수가 아닌 수는 합성수라고 부르며, 더 작은 정수들의 곱으로 나타낼 수 있습니다. 이 계산기는 입력한 숫자가 소수인지 즉시 알려주고, 소수가 아니라면 그 수를 나누는 가장 작은 약수까지 보여줍니다.

소수는 직사각형을 만들 수 없지만(\(1 \times n\) 제외), 합성수는 만들 수 있습니다.

계산기 사용 방법

입력란에 0 이상의 정수를 입력한 뒤 확인을 누르세요. 결과 박스에는 해당 숫자가 소수이면 예(YES), 합성수이면 아니오(NO)가 표시됩니다. 합성수인 경우에는 1보다 큰 가장 작은 약수가 표에 나타나는데, 이는 전체 소인수분해를 시작하는 출발점으로 활용할 수 있습니다.

공식 자세히 살펴보기

소수 여부를 효율적으로 확인하려면 \(n\)의 제곱근까지의 약수만 검사하면 됩니다. 만약 \(n\)이 제곱근보다 큰 약수를 가진다면, 반드시 제곱근보다 작은 짝이 되는 약수도 함께 존재하기 때문에 그 지점까지만 확인하면 충분합니다. 수식으로 표현하면, \(n > 1\)이고 2부터 \(\lfloor\sqrt{n}\rfloor\)까지의 모든 정수 \(i\)에 대해 \(n \bmod i \neq 0\)일 때 \(n\)은 소수입니다.

$$n \text{ is prime} \iff n > 1 \text{ and } n \bmod i \neq 0 \;\; \forall\, i \in [2, \sqrt{n}]$$

이 방법은 \(n\)보다 작은 모든 수를 일일이 검사하는 것보다 계산량을 크게 줄여 줍니다.

약수는 \(n\)의 제곱근까지만 확인하면 됩니다.

예제로 이해하기

\(n = 97\)을 살펴봅시다. 제곱근이 약 \(9.85\)이므로 약수 2, 3, 5, 7, 9만 검사하면 됩니다. 97은 홀수이고 3, 5, 7로도 나누어떨어지지 않으므로 어느 것도 97을 정확히 나누지 못합니다. 따라서 97은 소수입니다. 이번에는 \(n = 91\)을 봅시다. 2, 3, 5를 차례로 검사한 뒤 7을 시도하면 \(91 \div 7 = 13\)으로 딱 떨어집니다. 그러므로 91은 가장 작은 약수가 7인 합성수입니다.

자주 묻는 질문

1은 소수인가요? 아닙니다. 정의상 소수는 1보다 커야 하므로, 1은 소수도 합성수도 아닙니다.

2는 소수인가요? 네. 2는 유일한 짝수 소수입니다. 2를 제외한 모든 짝수는 2로 나누어떨어지기 때문입니다.

왜 제곱근까지만 검사하나요? 약수는 곱해서 \(n\)이 되는 짝으로 존재합니다. 만약 두 약수가 모두 \(\sqrt{n}\)보다 크다면 그 곱이 \(n\)을 넘어서게 되어 모순이 됩니다. 따라서 모든 약수 짝에서 적어도 하나는 반드시 \(\sqrt{n}\) 이하입니다.