소수 판별기
숫자를 입력하여 소수 여부를 확인하고, 구간 내 소수 목록 및 소인수분해 결과를 구합니다.
소수 안내
소수(Prime Number)란 1과 자기 자신만을 약수로 가지는 1보다 큰 양의 정수입니다.
소수 판별법(Trial Division): 2부터 √n 이하의 수로 나누어지지 않으면 소수입니다.
소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ... 으로 무한히 존재합니다.
계산 예시
97은 소수입니다. √97 ≈ 9.85 이하의 어떤 수로도 나누어떨어지지 않으므로 약수는 1과 97뿐입니다.
1부터 50까지의 소수는 15개입니다. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47입니다.
이 판별의 한계
2 이상의 정수만 의미가 있습니다. 1은 소수도 합성수도 아니고 0과 음수는 대상이 아닙니다. 제곱근까지만 나눠보는 방식이라 정확하지만 아주 큰 수에서는 느려지며, 암호에서는 밀러-라빈 같은 확률적 검사를 씁니다.
자주 묻는 질문
- 1은 왜 소수가 아닌가요?
- 소수는 약수가 1과 자기 자신, 정확히 두 개여야 합니다. 1은 약수가 하나뿐이고, 1을 제외해야 소인수분해가 유일해집니다.
- 소수는 몇 개나 있나요?
- 무한히 많습니다. 유클리드는 알려진 모든 소수를 곱해 1을 더한 수는 그 어느 소수로도 나누어떨어지지 않으므로 더 큰 소수가 반드시 존재한다고 증명했습니다.
- 제곱근까지만 확인해도 되는 이유는?
- n = a × b라면 두 인수 중 적어도 하나는 √n 이하입니다. 따라서 √n까지 약수가 없으면 그보다 큰 약수도 존재할 수 없습니다.