소수란 무엇인가 — 정의와 판별 원리
소수는 1과 자기 자신만을 약수로 갖는, 즉 약수가 정확히 2개인 1보다 큰 자연수입니다. 약수가 더 많으면 합성수입니다. 이 도구는 √n까지만 나눠보며, 그것으로 모든 약수를 찾을 수 있습니다. 이때 1부터 √n까지의 정수를 순서대로 모두 시험하며, 소수인 후보만 골라내지 않고 4나 6처럼 합성수인 후보도 그대로 나눠봅니다.
- n — 판별할 수
- i — √n까지 시험하는 약수 후보
자세한 설명
왜 √n까지만 확인하면 되나
약수는 곱해서 n이 되는 짝으로 나옵니다 — 36이면 2와 18, 3과 12, 4와 9, 6과 6처럼요. 근거: n이 합성수라서 n = a × b로 쓸 수 있다고 할 때, a와 b가 둘 다 √n보다 크다고 가정하면 a × b는 반드시 n보다 커집니다. 이는 a × b = n이라는 전제와 모순되므로, a와 b 중 적어도 하나는 √n 이하여야 합니다. 그러므로 1부터 √n까지의 정수만 나눠봐도 n의 약수를 빠짐없이 찾을 수 있습니다. 17은 √17 ≈ 4.12이므로 시험 대상이 1, 2, 3, 4뿐입니다. 이 범위를 넘어서까지 나눠보는 것은 이미 찾은 약수의 짝을 중복해서 확인하는 셈이라 불필요합니다.
계산 과정 — 97이 소수인지 확인하기
√97 ≈ 9.85이므로 1부터 9까지의 정수로 97을 나눠 나머지를 확인합니다. 이 계산기의 코드는 소수만 골라 시험하지 않고 1, 2, 3, 4, 5, 6, 7, 8, 9를 순서대로 전부 나눠봅니다 — 4나 6, 8, 9처럼 그 자체로 합성수인 후보도 똑같이 시도합니다. 97 ÷ 1 = 97(항상 나누어떨어져 약수 1과 97 확보), 97 ÷ 2는 나머지 1(97은 홀수), 97 ÷ 3은 나머지 1(9+7=16은 3의 배수가 아님), 97 ÷ 4는 나머지 1, 97 ÷ 5는 나머지 2(끝자리가 5나 0이 아님), 97 ÷ 6은 나머지 1, 97 ÷ 7은 나머지 6(97 = 7 × 13 + 6), 97 ÷ 8은 나머지 1, 97 ÷ 9는 나머지 7 — 1을 빼면 어느 것도 나누어떨어지지 않습니다. 그 결과 97의 약수는 1과 97 두 개뿐이므로 97은 소수입니다.
왜 1은 소수가 아닌가
소수의 정의를 그렇게 잡는 이유는 산술의 기본정리 때문입니다. 이 정리는 1보다 큰 모든 자연수가 소수들의 곱으로 유일하게(순서를 무시하면) 분해된다고 말합니다. 만약 1을 소수로 인정하면 이 유일성이 깨집니다. 예를 들어 12 = 2² × 3인데, 1을 소수로 치면 12 = 1 × 2² × 3 = 1² × 2² × 3 = 1³ × 2² × 3처럼 1을 몇 번이든 곱해 넣을 수 있어 분해 방식이 무한히 늘어납니다. 그래서 1은 소수의 정의에서 제외되고, 소수도 합성수도 아닌 특수한 경우로 다룹니다. 소수는 약수가 정확히 2개(1과 자기 자신)여야 하는데, 1의 약수는 1 하나뿐이라는 점에서도 정의를 만족하지 못합니다.
2는 유일한 짝수 소수다
2보다 큰 짝수는 모두 2로 나누어떨어지므로 약수가 최소 1, 2, 자기 자신 셋 이상이 되어 소수가 될 수 없습니다. 그래서 짝수 중 소수는 2 하나뿐입니다. 다만 이 계산기의 코드를 보면 2를 따로 걸러내거나 짝수를 건너뛰는 별도 처리는 없습니다 — 시험 약수 i를 1부터 √n까지 1씩 늘려가며 순서대로 n을 나눠볼 뿐이라, 홀수든 짝수든 합성수든 구분 없이 모두 시도합니다. 다만 계산 결과 자체는 정확합니다. 예를 들어 4를 넣으면 확인하는 도중 i=2에서 나누어떨어져 약수 1, 2, 4를 찾아내고 개수가 3개이므로 합성수로 판정합니다. 반대로 2를 넣으면 √2 ≈ 1.41이라 시험 대상이 1뿐이라, 약수는 1과 2 두 개로 확정되어 소수로 판정합니다.
소수는 무한히 많다 — 유클리드의 증명
소수가 유한 개라고 가정하고 그 전부를 곱한 뒤 1을 더하면 모순이 생긴다는 것이 유클리드의 증명입니다. 예를 들어 2×3×5×7×11×13 = 30,030이고, 여기에 1을 더하면 30,031입니다. 이 30,031을 기존 소수 목록(2, 3, 5, 7, 11, 13) 중 어느 것으로 나눠도 항상 나머지 1이 남아 나누어떨어지지 않습니다. 그렇다고 30,031 자체가 소수라는 뜻은 아닙니다 — 실제로 30,031 = 59 × 509이고, 59와 509는 둘 다 소수이지만 원래 목록 여섯 개에는 없던 새로운 소수입니다. 증명의 핵심은 '곱하고 1을 더하면 소수가 나온다'가 아니라, '목록에 없는 새로운 소수가 적어도 하나는 반드시 존재한다'는 것입니다. 목록이 유한하다는 가정 자체가 매번 무너지므로 소수는 무한히 많습니다. 이 논증은 기원전 3세기 유클리드의 원론에 처음 기록된 이래 지금도 그대로 성립합니다. 소수 목록이 아무리 길어도 이 과정을 한 번 더 반복하면 목록에 없던 소수가 또 나오므로, 소수 목록에는 끝이 없다는 결론을 피할 수 없습니다.
큰 수의 소수 판정은 시험 나눗셈으로 안 된다
이 계산기처럼 1부터 √n까지 순서대로 나눠보는 시험 나눗셈은 자릿수가 큰 수에서는 감당이 안 됩니다. n이 100자리쯤 되면 √n도 50자리에 달해, 그만큼의 후보를 하나씩 나눠보는 데 현실적인 시간이 걸리지 않습니다. 그래서 암호학 등에서 큰 수를 다룰 때는 밀러-라빈 같은 확률적 소수 판정법을 씁니다. RSA 같은 공개키 암호 방식은 두 개의 큰 소수를 곱해 만든 합성수를 다시 소인수분해하기 어렵다는 사실에 의존합니다 — 구체적인 키 길이나 알고리즘 내부 단계는 이 페이지의 범위를 벗어나 다루지 않습니다. 출처: 시험 나눗셈의 시간 복잡도와 산술의 기본정리는 초등 정수론의 표준 결과입니다. 이 설명의 기준일은 2026년입니다. 이 계산기는 교육·검산용으로 시험 나눗셈만 구현하며, 확률적 판정법은 다루지 않습니다.
빠른 선별 팁. 3보다 큰 소수는 모두 6k ± 1 꼴입니다. 2나 3이 아니면서 6의 배수 양옆에 있지 않은 수는 소수가 될 수 없어요 — 나눗셈 전에 머릿속으로 빠르게 거를 수 있습니다. 다만 이 계산기 자체는 이 필터를 쓰지 않고 1부터 √n까지의 모든 정수를 순서대로 그대로 시험합니다.
자주 묻는 질문
17은 소수인가요?
네. 17의 약수는 1과 17(2개)뿐이라 소수입니다. 위에 17을 입력하면 약수 목록과 개수를 확인할 수 있습니다. √17 ≈ 4.12이므로 이 계산기는 1, 2, 3, 4를 차례로 나눠보고, 1과 17을 제외하면 나누어떨어지는 수가 없어 소수로 판정합니다.
1은 소수인가요?
아닙니다. 소수는 서로 다른 약수가 정확히 2개여야 하는데 1은 약수가 자기 자신 하나뿐입니다. 관례상 1은 소수도 합성수도 아니며, 이 도구는 '소수 아님'으로 표시합니다.
12는 왜 합성수인가요?
12의 약수는 1, 2, 3, 4, 6, 12로 6개라 2개보다 많으므로 합성수(소수 아님)입니다. 위에 12를 입력하면 약수가 모두 나열됩니다. √12 ≈ 3.46이므로 이 계산기는 1, 2, 3만 나눠보는데, 2에서 약수 쌍 2와 6이, 3에서 약수 쌍 3과 4가 각각 나와 총 6개의 약수가 모입니다.
가장 작은 소수는 무엇인가요?
2입니다. 다른 짝수는 모두 2로 나눠지므로 2는 유일한 짝수 소수입니다. 그다음 소수는 3, 5, 7, 11, 13 순입니다.
0은 소수인가요?
이 계산기는 1 이상의 자연수만 판별 대상으로 삼습니다. 0을 넣으면 판별 범위 밖이라 소수·합성수 여부를 정하지 않고 결과란이 모두 물결표(—)로 표시됩니다. 수학적으로도 소수는 1보다 큰 자연수 중 약수가 정확히 2개인 수로 정의되므로, 0은 애초에 그 정의의 대상이 아닙니다. 음수나 소수점이 있는 수를 넣어도 같은 방식으로 처리되어, 정수가 아니거나 1보다 작은 값은 모두 판별 범위 밖으로 취급합니다.