소인수분해 계산기

소인수분해란?

소인수분해(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)

최대공약수(GCD)와 최소공배수(LCM) 계산

소인수분해는 GCD와 LCM을 구하는 가장 확실한 방법입니다.

GCD(최대공약수): 공통 소인수, 작은 지수

• 60 = 2² × 3 × 5
• 360 = 2³ × 3² × 5
• GCD = 2² × 3¹ × 5¹ = 60

LCM(최소공배수): 모든 소인수, 큰 지수

• 12 = 2² × 3
• 18 = 2 × 3²
• LCM = 2² × 3² = 36

소인수분해와 암호화의 관계

소인수분해는 현대 암호학의 핵심 기반입니다.

• RSA 암호화: 두 큰 소수(p, q)를 곱해 N = p × q를 만들면, N을 다시 p와 q로 분리하는 것(소인수분해)이 매우 어렵습니다.
• 예: 15자리 수의 소인수분해는 컴퓨터도 빠르게 계산하지만, 200자리 이상의 수는 현재 기술로도 수천 년이 걸립니다.
• 인터넷 뱅킹, HTTPS, 전자서명 등이 이 원리를 이용합니다.

소수의 개수와 분포

소수는 수가 커질수록 드물게 나타나지만, 무한히 많습니다.