소인수분해 계산기

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

소인수분해

1보다 큰 모든 정수는 소수들의 곱으로 나타낼 수 있습니다. 이 표현을 소인수분해라고 합니다. 예를 들어:

$360 = 2^3 \cdot 3^2 \cdot 5$

소수 2, 3, 5는 360의 '원자'입니다 — 더 이상 나누어지지 않습니다. 지수(3, 2, 1)는 각 소수가 곱에 몇 번 등장하는지를 나타냅니다.

산술의 기본 정리

산술의 기본 정리는 두 가지를 보장합니다.

1. 존재성: 1보다 큰 모든 정수는 소인수분해가 적어도 하나 존재합니다.
2. 유일성: 인수의 순서를 제외하면 그 분해는 단 하나입니다.

1이 소수가 아닌 이유: 1을 소수로 보면 360 = 1 · 2³ · 3² · 5 = 1² · 2³ · 3² · 5 처럼 무한히 많은 분해가 생깁니다. 1을 소수에서 제외해야 유일성이 유지됩니다.

시험 나눗셈 단계별 풀이

가장 직접적인 방법은 시험 나눗셈입니다. 2부터 $\sqrt{n}$까지의 정수를 순서대로 나누어 봅니다.

n = 360의 경우:

1. 2로 나누어 떨어지나요? 예: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45. 45는 홀수이므로 2로 더 이상 나눌 수 없습니다. 인수 2³ 확정.
2. 3으로 나누어 떨어지나요? 예: 45 ÷ 3 = 15, 15 ÷ 3 = 5. 5는 3으로 나누어지지 않습니다. 인수 3² 확정.
3. 5로 나누어 떨어지나요? 예: 5 ÷ 5 = 1. 인수 5¹ 확정.
4. 몫이 1이 되었으므로 완료. 결과: $360 = 2^3 \cdot 3^2 \cdot 5$.

왜 $\sqrt{n}$까지만 확인해도 될까요? n에 p > $\sqrt{n}$인 소인수가 있다면 n/p < $\sqrt{n}$이므로 더 작은 인수가 반드시 존재합니다. $\sqrt{n}$까지 인수가 발견되지 않으면 n 자체가 소수입니다.

소인수 나무

소인수 나무는 소인수분해를 시각화하는 방법입니다. 숫자를 임의의 두 인수로 나누고, 모든 가지가 소수로 끝날 때까지 반복합니다.

         360
        /    \
       8      45
      / \    /  \
     4   2  9    5
    / \    / \
   2   2  3   3

잎 노드를 모으면 2, 2, 2, 3, 3, 5 → 2³ · 3² · 5. 나무를 어떻게 그리든 결과는 항상 같습니다 — 유일성의 직관적인 확인입니다.

소인수분해로 약수 개수 구하기

소인수분해를 알면 단 하나의 공식으로 양의 약수의 총 개수를 구할 수 있습니다.

$\tau(n) = (e_1+1)(e_2+1)\cdots(e_k+1)$

왜 이 공식이 성립할까요? n의 각 약수는 소수 $p_i$에 대해 0부터 $e_i$까지의 지수를 독립적으로 선택하면 만들 수 있습니다. 소수마다 $(e_i+1)$가지의 선택지가 있고, 이 선택들은 독립적이므로 곱해집니다.

360의 약수 개수:

$\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$

360의 양의 약수는 정확히 24개입니다.

소인수분해로 최대공약수·최소공배수 구하기

두 수의 소인수분해를 알면 최대공약수(GCD)와 최소공배수(LCM)를 바로 읽어낼 수 있습니다.

• 최대공약수(GCD): 각 소수의 지수 중 작은 값을 선택합니다.
• 최소공배수(LCM): 각 소수의 지수 중 큰 값을 선택합니다.

예: 360과 504의 GCD·LCM

$360 = 2^3 \cdot 3^2 \cdot 5, \qquad 504 = 2^3 \cdot 3^2 \cdot 7$

소수	360의 지수	504의 지수	최솟값 (GCD)	최댓값 (LCM)
2	3	3	3	3
3	2	2	2	2
5	1	0	0	1
7	0	1	0	1

$\gcd(360, 504) = 2^3 \cdot 3^2 = 72, \qquad \text{lcm}(360, 504) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$

분수 약분

$\dfrac{a}{b}$를 기약분수로 만들려면 분자와 분모를 $\gcd(a, b)$로 나눕니다.

$\frac{360}{504} = \frac{360 \div 72}{504 \div 72} = \frac{5}{7}$

소인수분해의 응용

분야	활용 방법
암호학(RSA)	두 큰 소수의 곱을 인수분해하기 어렵다는 사실을 보안의 근거로 삼음
해시 테이블	소수 크기를 사용하면 충돌이 균일하게 분산됨
코딩 이론	오류 수정 코드의 생성 다항식
음악 이론(순정률)	음정 비율은 2, 3, 5의 거듭제곱의 비율로 표현됨

특수 경우

• n = 2(가장 작은 소수): 소인수분해는 2 자체; 약수는 정확히 2개.
• n이 소수: 소인수 하나; 약수 개수 = 2.
• n이 소수의 거듭제곱(예: 1024 = 2¹⁰): 서로 다른 소인수 1개; 약수 개수 = 11.
• 고도 합성수(360, 720, 1260…): 같은 크기의 수 중에서 약수가 가장 많은 수.

빠른 참조

개념	공식
소인수분해	$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$
서로 다른 소인수 개수	$\omega(n) = k$
약수의 총 개수	$\tau(n) = \prod (e_i + 1)$
두 수의 최대공약수	최솟값 지수의 곱
두 수의 최소공배수	최댓값 지수의 곱
항등식	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$

자주 묻는 질문 (FAQ)

소인수분해란 무엇인가요?

소인수분해란 1보다 큰 정수를 소수들의 곱으로 나타내는 것입니다. 예를 들어 360 = 2³ × 3² × 5입니다. 산술의 기본 정리에 따라 이 표현은 인수의 순서를 제외하면 유일하며, 약수·최대공약수·최소공배수 계산의 토대가 됩니다.

소인수분해는 왜 유일한가요?

산술의 기본 정리는 1보다 큰 모든 정수가 정확히 하나의 소인수분해를 가진다고 보장합니다(인수의 순서 제외). 이 유일성 덕분에 최대공약수(GCD)와 최소공배수(LCM)를 명확하게 정의할 수 있으며, RSA 암호화의 보안 근거이기도 합니다.

소인수분해로 약수의 개수를 어떻게 구하나요?

n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ 일 때, 양의 약수의 개수는 τ(n) = (e₁+1)(e₂+1)…(eₖ+1)입니다. 360 = 2³ × 3² × 5¹의 경우 τ(360) = 4 × 3 × 2 = 24이므로, 360의 약수는 정확히 24개입니다.

이 계산기로 다룰 수 있는 최대 수는 얼마인가요?

이 계산기는 최대 1,000,000,000,000(10¹², 1조)까지 지원합니다. √n까지의 시험 나눗셈을 사용하며 최대 약 100만 번의 반복으로 완료되어 브라우저에서도 충분히 빠릅니다. 더 큰 수의 소인수분해에는 Pollard rho 방법이나 이차 체 등의 특수 알고리즘이 사용됩니다.