🔢
2 이상의 자연수를 입력하세요
계산 공식
N = p₁^a₁ × p₂^a₂ × ... (p: 소수, a: 지수)소인수분해란?
소인수분해(Prime Factorization)는 자연수를 소수(Prime Number)만의 곱으로 나타내는 것입니다. 소수는 1과 자기 자신으로만 나누어지는 수(2, 3, 5, 7, 11, 13, ...)입니다. 산술의 기본 정리(Fundamental Theorem of Arithmetic)에 따르면, 1보다 큰 모든 자연수는 소인수분해가 유일합니다(순서 무관).
예) 60 = 2² × 3 × 5
소인수분해 방법 — 나눗셈법
가장 작은 소수부터 차례로 나누는 방법입니다.
예시 1: 60 소인수분해
60 ÷ 2 = 30 → 30 ÷ 2 = 15 → 15 ÷ 3 = 5 (소수) 결과: 2² × 3 × 5
예시 2: 360 소인수분해
360 ÷ 2 = 180 → 180 ÷ 2 = 90 → 90 ÷ 2 = 45 → 45 ÷ 3 = 15 → 15 ÷ 3 = 5 (소수) 결과: 2³ × 3² × 5
예시 3: 720 소인수분해
720 = 2⁴ × 3² × 5 → 약수의 개수: (4+1)(2+1)(1+1) = 30개
약수의 개수 공식
소인수분해가 p^a × q^b × r^c 이면:
- 약수의 개수 = (a+1) × (b+1) × (c+1)
| 수 | 소인수분해 | 약수 개수 | 모든 약수 |
|---|---|---|---|
| 12 | 2² × 3 | (2+1)(1+1) = 6 | 1,2,3,4,6,12 |
| 30 | 2 × 3 × 5 | (1+1)(1+1)(1+1) = 8 | 1,2,3,5,6,10,15,30 |
| 60 | 2² × 3 × 5 | (2+1)(1+1)(1+1) = 12 | 1,2,3,4,5,6,10,12,15,20,30,60 |
| 100 | 2² × 5² | (2+1)(2+1) = 9 | 1,2,4,5,10,20,25,50,100 |
최대공약수(GCD)와 최소공배수(LCM) 계산
소인수분해는 GCD와 LCM을 구하는 가장 확실한 방법입니다.
GCD(최대공약수): 공통 소인수, 작은 지수
예) GCD(60, 360) 계산:- 60 = 2² × 3 × 5
- 360 = 2³ × 3² × 5
- GCD = 2² × 3¹ × 5¹ = 60
LCM(최소공배수): 모든 소인수, 큰 지수
예) LCM(12, 18) 계산:- 12 = 2² × 3
- 18 = 2 × 3²
- LCM = 2² × 3² = 36
소인수분해와 암호화의 관계
소인수분해는 현대 암호학의 핵심 기반입니다.
- RSA 암호화: 두 큰 소수(p, q)를 곱해 N = p × q를 만들면, N을 다시 p와 q로 분리하는 것(소인수분해)이 매우 어렵습니다.
- 예: 15자리 수의 소인수분해는 컴퓨터도 빠르게 계산하지만, 200자리 이상의 수는 현재 기술로도 수천 년이 걸립니다.
- 인터넷 뱅킹, HTTPS, 전자서명 등이 이 원리를 이용합니다.
소수의 개수와 분포
소수는 수가 커질수록 드물게 나타나지만, 무한히 많습니다.
| 범위 | 소수 개수 |
|---|---|
| 1~10 | 4개 (2,3,5,7) |
| 1~100 | 25개 |
| 1~1,000 | 168개 |
| 1~10,000 | 1,229개 |
| 1~100,000 | 9,592개 |
자주 묻는 질문
소인수분해와 인수분해는 다른 건가요?
인수분해는 수나 식을 더 작은 인수들의 곱으로 나타내는 것이고, 소인수분해는 자연수를 소수(Prime Number)의 곱으로만 나타내는 것입니다. 소인수분해는 인수분해의 특수한 경우로, 최종 분해 결과가 모두 소수여야 합니다.
60의 소인수분해 결과는 무엇인가요?
60 = 2² × 3 × 5 입니다. 60 ÷ 2 = 30, 30 ÷ 2 = 15, 15 ÷ 3 = 5, 5는 소수이므로 2²(=4) × 3 × 5 = 60. 약수의 개수는 (2+1)(1+1)(1+1) = 12개입니다.
소인수분해는 유일한가요?
네, 산술의 기본 정리에 따라 1보다 큰 모든 자연수는 소인수분해가 유일합니다. 소인수를 나열하는 순서는 달라질 수 있지만, 어떤 방법으로 분해해도 결과는 동일합니다.
소인수분해는 어디에 활용되나요?
최대공약수(GCD)와 최소공배수(LCM) 계산, 약수의 개수 구하기, 분수 약분, 암호학(RSA 암호화는 큰 수의 소인수분해가 어렵다는 점을 이용)에 활용됩니다.
약수의 개수를 소인수분해로 구하는 방법은?
소인수분해 결과가 p^a × q^b × ...이면 약수의 개수 = (a+1)(b+1)...입니다. 예를 들어 72 = 2³ × 3²이면 약수의 개수 = (3+1)(2+1) = 12개입니다. 72의 약수: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
1은 소수인가요?
아닙니다. 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수입니다. 1은 이 정의에 맞지 않으며, 소인수분해의 유일성을 보장하기 위해 소수에서 제외합니다. 가장 작은 소수는 2입니다.
소인수분해로 두 수의 최대공약수를 구하려면?
두 수를 각각 소인수분해한 후 공통 소인수를 찾고, 작은 지수를 곱합니다. GCD(48, 36): 48 = 2⁴ × 3, 36 = 2² × 3². 공통 소인수는 2와 3이며, GCD = 2² × 3 = 12입니다.