소인수분해 계산기

소인수분해 쉽게 이해하기 — 개념과 원리

소인수분해는 1보다 큰 자연수를 소수들의 곱으로 나타내는 것으로, 360 = 2³ × 3² × 5처럼 씁니다. 분수와 근호를 간단히 하고, 최대공약수와 최소공배수를 구하고, 약수의 개수를 세는 데 바탕이 되는 기본 도구입니다. 이 계산기는 소인수분해 결과와 함께 약수의 개수와 약수의 합, 그 수가 소수인지도 알려 줍니다.

계산 방법

• 나눗셈 시험: n을 2로 나누어떨어지지 않을 때까지 나누고, 이어서 3, 5, 7…로 나누어 갑니다. 나누는 수가 √n보다 커지면 멈추고, 1보다 큰 수가 남아 있으면 그 수가 소수입니다.
• 약수의 개수: n = p₁^e₁ × p₂^e₂ × …이면 (e₁ + 1)(e₂ + 1)…입니다.
• 약수의 합: 각 소인수마다 (p^(e+1) − 1) ÷ (p − 1)을 구해 모두 곱합니다.

입력값은 2 이상, 약 9 × 10¹⁵ 이하의 자연수입니다.

원리

산술의 기본정리에 따르면 1보다 큰 모든 자연수의 소인수분해는 곱하는 순서를 무시하면 단 한 가지뿐입니다. √n까지만 나누어 보면 되는 이유는 n = a × b일 때 a와 b 중 적어도 하나는 √n 이하이기 때문입니다. n의 약수는 각 소인수의 지수를 0부터 e까지 따로따로 골라 만들므로, 소인수마다 e + 1가지 선택이 있고 이를 곱한 것이 약수의 개수입니다. 약수의 합은 1 + p + p² + … + pᵉ = (p^(e+1) − 1)/(p − 1)이라는 등비수열의 합을 소인수마다 곱한 것입니다.

예제 풀이

1. 입력값: 360입니다.
2. 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45이므로 2³입니다. 45 ÷ 3 = 15, 15 ÷ 3 = 5이므로 3²이고, 5는 소수입니다.
3. 소인수분해 결과는 2^3 × 3^2 × 5입니다.
4. 약수의 개수는 (3 + 1)(2 + 1)(1 + 1) = 24개입니다.
5. 약수의 합은 15 × 13 × 6 = 1,170입니다.
6. 소수인가요? 아니요(no)입니다.

결과 해석

소인수가 하나이고 지수가 1이면 그 수는 소수입니다. 360처럼 작은 소인수가 여러 개 있으면 약수가 많아 여러 방법으로 나누기 좋습니다. 원의 360°나 12, 24, 60 같은 단위가 여러 가지로 나누기 편리한 것도 이 때문입니다. 약수의 합이 2n보다 크면 과잉수이며, 360은 1,170 > 720이므로 과잉수입니다.

흔한 실수

• 1을 소수로 여깁니다. 1은 소수도 합성수도 아닙니다.
• 9나 15 같은 합성수가 남았는데 멈춥니다.
• 같은 소인수를 한 번만 씁니다. 360에는 2가 세 번 들어 있습니다.
• 약수의 개수를 지수끼리 곱해 구합니다. 지수에 1을 더해 곱해야 합니다.

자주 묻는 질문

소인수분해가 암호에서 왜 중요한가요?

큰 소수 두 개를 곱하기는 쉽지만, 곱한 결과에서 원래 소수를 찾기는 일반 컴퓨터로 매우 어렵습니다. RSA 암호가 이 차이를 이용합니다.

소인수분해로 제곱근을 어떻게 간단히 하나요?

같은 소인수를 두 개씩 묶어 밖으로 꺼냅니다. √360 = √(2² × 3² × 2 × 5) = 6√10입니다.

소인수분해 결과는 어떤 순서로 쓰나요?

보통 작은 소수부터 차례로 쓰고, 같은 소수는 거듭제곱으로 묶어 나타냅니다.

출처: G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Chapter 2, Chapter 16(산술 함수) · Euclid, Elements, Book VII 명제 30–32, Book IX 명제 14