소인수 분해 (prime factorization)

정의

어떤 자연수 n을 소수의 곱으로 표현하는 과정입니다.

소인수분해는 “숫자의 구조를 가장 기본 부품(소수)”로 분해하는 작업이라, 수학/알고리즘/암호학에서 반복해서 등장합니다.

예를 들어 12는 2 × 2 × 3(= 2² × 3)으로 표현됩니다. 

핵심 메시지

“소인수분해는 숫자를 소수라는 ‘부품’으로 분해하는 것이고,
이 부품은 유일하게 결정된다.”

- 기본정리(유일성)의 직관 -

핵심 성질

모든 자연수(2 이상)는 소수의 곱으로 유일하게 표현됩니다.

이 성질을 흔히 “정수의 기본정리”라고 부릅니다. 중요한 포인트는 “표현할 수 있다”뿐 아니라 표현이 하나로 정해진다(유일성)입니다. (순서만 다를 뿐 같은 소수들의 조합으로만 분해됩니다.)

방법

기본은 작은 소수부터 나눠 떨어지는 만큼 나누기입니다.

가장 단순한 방법은 2부터 시작해 나누어 떨어지는 동안 계속 나누는 방식입니다. 그리고 남은 수가 1이 되면 끝, 1이 아니라면 마지막 남은 값 자체가 소수입니다.

실무/코테에서 중요한 최적화 포인트는 √n까지만 나누어 보면 된다는 점입니다. 어떤 수 n이 합성수라면 n = a × b 형태이고, a 또는 b 중 하나는 반드시 √n 이하이기 때문입니다.

전략	복잡도 감각	언제 유리한가
단일 n 분해	O(√n)	입력이 하나(또는 소수의 개수가 적음)
여러 번 분해	사전 계산 필요	많은 쿼리/범위 처리(최소 소인수 배열 등)

💡 TIP / 코테 최적화

2를 먼저 처리한 뒤에는 홀수만 검사하면 절반으로 줄일 수 있습니다. 그리고 나누는 과정에서 n이 작아지면 √n도 같이 작아져 실제 실행은 더 빨라집니다.

예시

“나누어 떨어지는 만큼 반복”하는 과정입니다.

예시: 360
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5는 소수 → 종료

따라서 360 = 2³ × 3² × 5

활용

약수/최대공약수/최소공배수를 빠르게 다루는 기반이 됩니다.

• ✔️ 약수 개수: n = p₁^a × p₂^b… 이면 약수 개수는 (a+1)(b+1)…
• ✔️ GCD/LCM: 소인수 지수의 min/max로 계산(원리 이해용)
• ✔️ 암호학: 큰 수의 소인수분해가 어렵다는 성질을 이용하는 경우가 있음

코드

자바로 구현합니다.

for (int d = 2; d * d <= N; d++) {
	while (N % d == 0) {
		sb.append(d).append("\n");
		N /= d;
	}
}
if (N > 1) sb.append(N).append("\n");

주의점

큰 수는 단순 분해가 어렵고, 정수 범위/오버플로우를 조심해야 합니다.

코테 수준에서는 √n 분해로 충분한 경우가 많지만, 매우 큰 정수(암호학 수준)는 더 고급 알고리즘이 필요합니다. 또한 곱셈/제곱을 할 때 int 범위를 넘는 경우가 있으니 long 사용 등 자료형에도 주의해야 합니다.

핵심 요약

한 번에 정리

✅ 핵심 요약

• ✔️ 소인수분해는 자연수 n을 소수의 곱으로 표현하는 과정이다.
• ✔️ 기본 전략은 작은 소수부터 반복 나눗셈, 최적화는 √n까지만 검사다.
• ✔️ 약수/LCM/GCD/암호 등 다양한 문제의 기반이 되는 핵심 도구다.