결과 이해하기
아래 표는 예시 입력에 대한 세 가지 출력값을 보여줍니다.
| 입력 | 소수 여부 | 소인수분해 | 다음 소수 |
|---|---|---|---|
| 97 | 예 | 97 | 101 |
| 84 | 아니오 | 2 x 2 x 3 x 7 | 89 |
| 100 | 아니오 | 2 x 2 x 5 x 5 | 101 |
| 2 | 예 (유일한 짝수 소수) | 2 | 3 |
| 1 | 아니오 (소수도 합성수도 아님) | - | 2 |
- 1은 소수가 아닙니다. 소수는 서로 다른 약수를 정확히 두 개 가져야 하는데 1은 약수가 하나뿐입니다. 1을 제외해야 소인수분해의 유일성이 유지됩니다.
- 시행나눗셈은 정확하지만 입력이 매우 커지면 느려집니다. 이 계산기는 10^12까지의 수를 받으며, 이 경우 최대 100만까지의 약수를 검사합니다.
- 이 범위에서 다음 소수 탐색은 빠르게 종료됩니다. 베르트랑 공준에 따라 n과 2n 사이에는 항상 소수가 존재하기 때문입니다.
소수란 무엇입니까?
소수는 1보다 큰 자연수 중 양의 약수가 정확히 두 개, 즉 1과 자기 자신뿐인 수입니다. 처음 몇 개의 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29입니다. 2는 유일한 짝수 소수인데, 다른 모든 짝수는 2로 나누어떨어지기 때문입니다. 1보다 크면서 소수가 아닌 수는 합성수라고 부르며, 1은 정의상 소수도 합성수도 아닙니다.
산술의 기본 정리에 따르면 1보다 큰 모든 정수는 인수의 순서를 무시하면 정확히 한 가지 방법으로 소수의 곱으로 표현됩니다. 이처럼 소인수분해가 유일하기 때문에 소수를 정수의 구성 요소라고 부릅니다. 84 = 2^2 x 3 x 7이며, 84가 되는 다른 소수 조합은 존재하지 않습니다.
소수는 무한히 많으며, 이는 기원전 300년경 유클리드가 증명했습니다. 소수는 수가 커질수록 드물어지지만 단순한 규칙은 없습니다. 큰 소수는 현대 공개키 암호(예: RSA)의 기반이며, 이는 매우 큰 두 소수의 곱을 인수분해하기가 실제로 매우 어렵다는 점에 의존합니다.
이 소수 계산기 사용 방법
- 1 이상의 자연수 n을 입력합니다. 소수점이 있는 값은 가장 가까운 정수로 내림 처리됩니다.
- 소수 판정 결과를 확인합니다. 체크 표시는 소수임을, 가위표는 합성수(또는 소수도 합성수도 아닌 1)임을 뜻합니다.
- 소인수분해를 확인합니다. 입력한 수와 같은 값을 가지는 유일한 소수의 곱입니다. 입력이 소수이면 분해 결과는 그 수 자체입니다.
- 다음 소수를 확인합니다. 입력한 수보다 엄격히 큰 소수 중 가장 작은 수입니다.
소수 판정 방법: 시행나눗셈
어떤 수 n이 합성수일 필요충분조건은 1보다 크고 n의 제곱근 이하인 약수를 가지는 것입니다. 약수는 짝을 이루기 때문인데, n = a x b이고 a <= b이면 a <= sqrt(n)입니다. 따라서 시행나눗셈은 sqrt(n)까지의 후보 약수만 검사하면 되고, 2를 확인한 뒤에는 홀수 후보만 살펴보면 됩니다.
풀이 예시(소수): n = 97. 97의 제곱근은 약 9.85이므로 2, 3, 5, 7, 9만 검사하면 충분합니다. 97은 홀수이고, 9 + 7 = 16은 3으로 나누어떨어지지 않으며, 끝자리가 0이나 5도 아니고, 97 / 7 = 13.857...이며, 97 / 9도 정수가 아닙니다. 약수가 없으므로 97은 소수입니다.
풀이 예시(소인수분해): n = 84. 작은 소수부터 차례로 나눕니다. 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7이고 7은 소수입니다. 따라서 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7입니다. 84 다음 소수는 89입니다(85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
흔한 실수
- 1을 소수로 세는 것 — 정의상 소수는 서로 다른 약수를 정확히 두 개 가지는데 1은 하나뿐입니다.
- 모든 소수가 홀수라고 가정하는 것: 2는 소수이며 유일한 짝수 소수입니다.
- sqrt(n)에서 멈추지 않고 n까지 약수를 모두 검사하는 것 — 모든 합성수는 제곱근 이하의 인수를 가집니다.
- 모든 홀수가 소수라고 믿는 것: 9 = 3 x 3, 15 = 3 x 5, 21 = 3 x 7은 모두 홀수인 합성수입니다.
- 소인수분해를 임의의 인수분해와 혼동하는 것: 84 = 4 x 21도 인수분해이지만, 소인수분해는 2 x 2 x 3 x 7입니다.
자주 묻는 질문
어떤 수가 소수인지 어떻게 확인합니까?
2부터 그 수의 제곱근까지의 정수 중에 그 수를 나누어떨어지게 하는 것이 있는지 검사합니다. 하나도 없으면 그 수는 소수입니다. 97의 제곱근은 약 9.85이고 2, 3, 5, 7, 9 중 어느 것도 97을 나누지 못하므로 97은 소수입니다. 약수가 짝을 이룬다는 성질 덕분에 모든 합성수는 제곱근 이하의 인수를 반드시 가집니다.
1은 왜 소수가 아닙니까?
소수는 서로 다른 양의 약수를 정확히 두 개, 즉 1과 자기 자신을 가지는 수로 정의되는데, 1은 약수가 하나뿐입니다. 이 정의는 산술의 기본 정리도 보호합니다. 만약 1이 소수라면 분해가 더 이상 유일하지 않게 됩니다(6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3 등).
소인수분해란 무엇입니까?
어떤 수를 소수들의 곱으로 나타낸 것이며, 산술의 기본 정리에 따라 순서를 무시하면 유일합니다. 예를 들어 84 = 2 x 2 x 3 x 7입니다. 구하는 방법은 나누어떨어지는 가장 작은 소수로 반복해서 나누어, 남은 몫이 1이거나 소수가 될 때까지 계속하는 것입니다.
2는 소수입니까?
그렇습니다. 2의 약수는 1과 2뿐이므로 소수이며, 유일한 짝수 소수입니다. 다른 모든 짝수는 2로 나누어떨어지므로 합성수입니다. 그래서 소수 판정 알고리즘은 2를 따로 처리한 뒤 홀수 후보만 검사합니다.
소수는 몇 개나 있습니까?
무한히 많습니다. 기원전 300년경 유클리드가 증명했듯이, 소수의 유한한 목록이 주어졌을 때 그것들을 모두 곱하고 1을 더한 수는 목록의 어느 소수로도 나누어떨어지지 않으므로 목록에 없는 소수가 반드시 존재합니다. 소수는 수가 커질수록 드물어지며, 소수 정리에 따르면 n 부근의 소수 밀도는 대략 1 / ln(n)이지만 결코 끊기지 않습니다.
소수는 왜 암호학에서 중요합니까?
RSA 같은 공개키 시스템은 비대칭성에 기반합니다. 큰 소수 두 개를 곱하는 것은 쉽지만, 그 곱에서 원래 소수를 되찾는 것은 실제로 쓰이는 크기(수백 자리)에서 계산적으로 매우 어렵습니다. 보안 키가 이러한 곱으로 만들어지므로 소수 생성과 소수 판정은 핵심적인 암호 연산입니다.
참고 자료
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).