🔍
1 이상의 정수
계산 공식
소수: 약수가 1과 자기 자신뿐인 수 | 판별: n의 √ 이하 소수로 나눗셈 시도n의 제곱근 이하의 수로 나누어 떨어지면 소수가 아닙니다. 소인수 분해는 2부터 순서대로 나누어 소인수를 구합니다.
소수 판별 방법과 소인수분해
소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 약수가 정확히 2개(1과 자기 자신)인 수가 소수입니다.
소수 판별 — 시험 나눗셈(Trial Division)
n이 소수인지 판별하려면 2부터 √n 이하의 수로만 나눠보면 됩니다.
- 97이 소수인지 확인: √97 ≈ 9.85 → 2, 3, 5, 7로 나눠봄 → 전부 나머지 있음 → 소수
- 91이 소수인지 확인: √91 ≈ 9.5 → 7 × 13 = 91 → 소수 아님 (합성수)
에라토스테네스의 체 — 범위 내 소수 일괄 탐색
2~100 범위 내 소수를 구하는 알고리즘: 1. 2부터 100까지 나열 2. 2를 남기고 2의 배수 모두 제거 3. 3을 남기고 3의 배수 모두 제거 4. 5, 7, ... 반복 (√100 = 10 이하의 소수까지) 5. 남은 수가 모두 소수
처음 25개 소수 (100 이하)
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
소인수분해 주요 예시
합성수를 소수의 곱으로 분해하는 것이 소인수분해입니다. 최대공약수·최소공배수 계산의 기초입니다.
| 수 | 소인수분해 | 약수 개수 |
|---|---|---|
| 12 | 2² × 3 | (2+1)×(1+1) = 6개 |
| 60 | 2² × 3 × 5 | (2+1)×(1+1)×(1+1) = 12개 |
| 100 | 2² × 5² | (2+1)×(2+1) = 9개 |
| 360 | 2³ × 3² × 5 | (3+1)×(2+1)×(1+1) = 24개 |
| 1000 | 2³ × 5³ | (3+1)×(3+1) = 16개 |
소수의 특성
- 2는 유일한 짝수 소수 (모든 다른 짝수는 2의 배수)
- 소수는 무한히 많음 (유클리드 증명, 기원전 300년)
- 소수 분포: 클수록 소수의 밀도가 낮아짐 (소수 정리: n 이하 소수 수 ≈ n/ln(n))
- 100만 이하 소수 개수: 78,498개
- 쌍둥이 소수: 차이가 2인 소수 쌍 (예: 11과 13, 17과 19)
자주 묻는 질문
2는 왜 특별한 소수인가요?
2는 유일한 짝수 소수입니다. 2보다 큰 짝수는 모두 2의 배수이므로 약수가 1, 2, 자기 자신으로 3개 이상이 됩니다. 따라서 2를 제외한 모든 짝수는 소수가 아닙니다.
1은 왜 소수가 아닌가요?
소수의 정의는 '약수가 정확히 2개인 수'입니다. 1의 약수는 1뿐으로 1개입니다. 약수 개수 기준으로 1은 소수도 합성수도 아닌 별도 범주입니다. 또한 1을 소수로 정의하면 소인수분해의 유일성(산술의 기본 정리)이 성립하지 않습니다.
소수 판별에서 왜 √n까지만 나눠봐도 되나요?
n의 약수는 항상 쌍으로 존재합니다(a × b = n). 한 쪽이 √n보다 작으면 다른 쪽은 √n보다 큽니다. 따라서 √n 이하에서 약수를 발견하지 못하면 √n 초과 구간에도 약수가 없습니다. 예: 100 판별 시 √100=10까지만 확인하면 됩니다.
큰 수의 소인수분해는 왜 어렵나요?
소인수분해 난이도는 수의 크기에 따라 기하급수적으로 증가합니다. 100자리 수 소인수분해는 현재 컴퓨터로도 수십억 년이 걸릴 수 있습니다. 이 원리가 RSA 암호화의 보안 기반입니다. 이 계산기는 1,000만 이하 수의 소인수분해를 즉시 처리합니다.