소수 판별기

최종 업데이트: 2026-05-18

소수의 정의

소수는 1보다 큰 자연수 중 1과 자기 자신 외에 양의 약수가 없는 수입니다. 다른 정수로는 나누어 떨어지지 않는다는 뜻입니다.

• 2 는 소수: 1과 2로만 나누어짐
• 7 은 소수: 1과 7로만 나누어짐
• 12 는 합성수: 1, 2, 3, 4, 6, 12로 나누어짐

첫 스무 개의 소수는 다음과 같습니다.

$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71$

소수는 숫자가 커질수록 드물어지지만 절대 멈추지 않습니다. 유클리드는 기원전 약 300년에 소수가 무한히 많음을 증명했습니다.

1이 소수가 아닌 이유

직관적으로는 1이 1과 자기 자신으로만 나누어지니 소수처럼 보일 수 있습니다. 그러나 현대 정의는 양의 약수가 정확히 두 개여야 한다고 요구하며, 1은 하나(자기 자신)밖에 없습니다.

더 깊은 이유는 산술의 기본 정리를 보존하기 위함입니다: 1보다 큰 모든 정수는 소수의 곱으로 유일하게 분해됩니다. 1을 소수로 정의하면 이 유일성이 무너집니다.

$12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^2 \times 2^2 \times 3 = \ldots$

따라서 1은 단위원이라 불리며, 소수도 합성수도 아닙니다.

이 계산기의 작동 방식: 시험 나눗셈

1부터 1000까지의 정수에 대해 이 도구는 시험 나눗셈을 사용합니다. $n$이 $\sqrt{n}$ 이하의 소수로 나누어지지 않으면, $n$은 소수입니다.

$\sqrt{1000} \approx 31.6$이므로, 31 이하의 소수(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31) 총 열한 개를 확인하면 1~1000의 모든 정수의 소수 판별이 가능합니다.

예시 — 97은 소수인가?

제수	$97 \div d$	나머지
2	48.5	1
3	32.3…	1
5	19.4	2
7	13.857…	6

$\sqrt{97} \approx 9.8$ 이하의 소수가 97을 나누지 못하므로 97은 소수입니다.

예시 — 91은 소수인가?

$91 \div 7 = 13$ (나머지 0). 7로 나누어지므로 91은 합성수($91 = 7 \times 13$)이며, 최소 소인수는 7입니다.

에라토스테네스의 체

어떤 상한까지의 모든 소수를 찾으려면 에라토스테네스의 체가 더 효율적입니다.

1. 2부터 $N$까지의 모든 정수를 나열합니다.
2. 2의 배수(4, 6, 8, …)를 지웁니다.
3. 지워지지 않은 다음 수(3)의 배수를 지웁니다.
4. $\sqrt{N}$에 도달할 때까지 반복합니다.

지워지지 않고 남은 수가 모두 소수입니다. 시간 복잡도는 $O(N \log \log N)$입니다.

소수와 암호학

공개 키 암호학의 대부분은 핵심적인 비대칭성에 기반합니다. 두 개의 큰 소수를 곱하는 것은 빠르지만, 그 곱을 다시 두 소수로 분해하는 것은 계산적으로 불가능합니다.

RSA 암호화(HTTPS, 디지털 서명에 사용):

1. 두 개의 큰 소수 $p$와 $q$를 선택합니다(보통 1024~4096비트).
2. $n = p \times q$를 계산하고 공개 키의 일부로 공개합니다.
3. 공격자가 암호를 해독하려면 $n$을 인수분해해야 하는데, 현재 컴퓨터로는 우주의 나이보다 긴 시간이 소요됩니다.

이 단방향 함수가 현대 인터넷 보안 통신의 토대를 이룹니다.

빠른 참조표

수	소수?	최소 소인수
1	아니오(단위원)	—
2	예	2(자신)
4	아니오	2
17	예	17(자신)
49	아니오	7
97	예	97(자신)
100	아니오	2
997	예	997(자신)

자주 묻는 질문 (FAQ)

소수란 무엇인가요?

소수는 1보다 큰 자연수 중에서 1과 자기 자신 외의 양의 약수가 없는 수입니다. 예를 들어 2, 3, 5, 7, 11, 13은 모두 소수입니다. 12는 2, 3, 4, 6으로 나누어지므로 소수가 아닙니다. 1보다 큰 모든 정수는 소수이거나 소수의 곱으로 유일하게 표현됩니다 — 이를 산술의 기본 정리라고 합니다.

1은 왜 소수가 아닌가요?

소수는 양의 약수가 정확히 두 개(1과 자기 자신)여야 합니다. 1의 양의 약수는 자기 자신뿐이므로 소수 조건을 충족하지 않습니다. 만약 1을 소수로 정의하면 소인수분해의 유일성이 깨집니다. 예를 들어 12 = 2² × 3 = 1 × 2² × 3 = 1² × 2² × 3 … 처럼 무수히 많은 분해가 생깁니다.

처음 열 개의 소수는 무엇인가요?

처음 열 개의 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29입니다. 2는 유일한 짝수 소수이며, 나머지 짝수는 모두 2로 나누어지므로 소수가 아닙니다. 기원전 약 300년에 유클리드는 소수가 무한히 많음을 증명했습니다.

소수가 암호학에서 중요한 이유는 무엇인가요?

RSA를 포함한 대부분의 공개 키 암호화 방식은 두 개의 큰 소수를 곱하기는 쉽지만, 그 곱으로부터 원래의 소수를 다시 찾아내는 것은 사실상 불가능하다는 비대칭성에 기반합니다. 현대 RSA 키는 수백 자리의 소수를 사용하며, 이 어려움이 HTTPS와 디지털 서명의 보안을 보장합니다.