소수 판별기

소수(prime number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 2, 3, 5, 7, 11, 13처럼 두 개의 약수만 갖는 수가 소수이며, 약수가 셋 이상인 4, 6, 8, 9는 합성수로 분류됩니다.

소수는 모든 자연수를 구성하는 '곱셈의 원자'와 같습니다. 산술의 기본 정리에 따라 1보다 큰 모든 자연수는 소수의 곱으로 유일하게 분해되기 때문입니다.

왜 중요한가

• 암호학: RSA 공개키 암호는 큰 두 소수의 곱을 다시 인수분해하기 어렵다는 성질에 안전성을 둡니다.
• 약분과 분수: 분자·분모의 소인수를 알면 기약분수로 쉽게 줄일 수 있습니다.
• 수론 연구: 소수는 무한히 많지만(유클리드의 증명) 그 분포는 여전히 미해결 난제로 남아 있습니다.

이 판별기는 시행 나눗셈(trial division)에 6k±1 최적화를 적용합니다. n이 합성수라면 약수 하나는 반드시 √n 이하이므로, 2와 3으로 먼저 거른 뒤 5부터 i*i ≤ n 동안 i와 i+2만 검사합니다.

핵심 조건: n < 2 → 소수 아님, 그리고 n % i === 0이 한 번이라도 참이면 합성수입니다.

예를 들어 97은 √97 ≈ 9.85이므로 2, 3, 5, 7로만 나눠 보면 됩니다. 97은 모두 나누어떨어지지 않아 소수입니다. 반면 91은 91 ÷ 7 = 13이므로 91 = 7 × 13인 합성수입니다.

소인수분해는 작은 소수부터 차례로 나누어, 같은 인수를 거듭제곱으로 묶어 표기합니다. 예: 360 = 2³ × 3² × 5.