소인수분해 계산기

소인수분해 계산기 - 숫자 분해

🔢 어떤 숫자든 소인수로 분해하세요. 곱셈 형태, 지수 표기, 인수 트리 시각화, 단계별 나눗셈 과정을 확인할 수 있습니다.

소인수분해란?

소인수분해(정수의 인수분해)는 합성수를 소수의 곱으로 나타내는 과정입니다. 모든 합성수는 고유한 소인수분해를 가집니다.

산술의 기본정리

1보다 큰 모든 정수는 (인수의 순서를 제외하고) 소수의 곱으로 유일하게 표현됩니다. 이는 수론에서 가장 중요한 정리 중 하나입니다.

표현 방식

곱셈 형태: 2 × 2 × 3 × 5

지수 형태: 2² × 3 × 5

지수 표기(인덱스): 2² · 3¹ · 5¹

예시

예시 1: 12

• 12 = 2 × 2 × 3
• 12 = 2² × 3
• 소인수: 2, 3

예시 2: 60

• 60 = 2 × 2 × 3 × 5
• 60 = 2² × 3 × 5
• 소인수: 2, 3, 5

예시 3: 100

• 100 = 2 × 2 × 5 × 5
• 100 = 2² × 5²
• 소인수: 2, 5

분해 방법

1. 시행 나눗셈(Trial Division):

• 작은 소수(2, 3, 5, 7...)로 나눕니다
• 몫이 1이 될 때까지 계속합니다
• 간단하지만 큰 수에서는 느릴 수 있습니다

2. 인수 트리:

• 수를 임의의 두 인수로 분해합니다
• 모든 인수가 소수가 될 때까지 계속합니다
• 시각적이고 이해하기 쉽습니다

3. 소수로만 나누기:

• 소수로만 나눕니다
• 모든 수를 시도하는 것보다 효율적입니다
• 컴퓨터에서 표준적으로 사용하는 알고리즘입니다

단계별: 60 분해

60 ÷ 2 = 30   (2는 소수)
30 ÷ 2 = 15   (2는 소수)
15 ÷ 3 = 5    (3은 소수)
5 ÷ 5 = 1     (5는 소수)

결과: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
            

모든 약수 찾기

소인수분해를 알면 모든 약수를 구할 수 있습니다:

예: 60 = 2² × 3¹ × 5¹

• 각 소인수의 지수를 0부터 최대값까지 선택합니다
• 2⁰ 또는 2¹ 또는 2² → (1, 2, 4)
• 3⁰ 또는 3¹ → (1, 3)
• 5⁰ 또는 5¹ → (1, 5)
• 모든 조합을 곱해 만듭니다
• 약수: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

약수의 개수 공식

n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ 일 때

약수의 개수 = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

예: 60 = 2² × 3¹ × 5¹

• 약수의 개수 = (2+1) × (1+1) × (1+1)
• = 3 × 2 × 2 = 12개

약수의 합 공식

합 = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ...

예: 60 = 2² × 3 × 5

• 합 = [(2³-1)/(2-1)] × [(3²-1)/(3-1)] × [(5²-1)/(5-1)]
• = [7/1] × [8/2] × [24/4]
• = 7 × 4 × 6 = 168

소인수분해의 활용

• 암호학: RSA 암호는 큰 수의 인수분해가 어렵다는 점을 이용합니다
• 최대공약수/최소공배수: GCD와 LCM 계산
• 분수 약분: 기약분수로 줄이기
• 정수론: 정수의 성질 연구
• 컴퓨터 과학: 해시 함수, 알고리즘

특별한 수의 종류

완전수:

• 자기 자신을 제외한 약수의 합이 자기 자신과 같음
• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14

과잉수:

• 자기 자신을 제외한 약수의 합이 자기 자신보다 큼
• 12: 약수의 합 = 1+2+3+4+6 = 16 > 12

부족수:

• 자기 자신을 제외한 약수의 합이 자기 자신보다 작음
• 8: 약수의 합 = 1+2+4 = 7 < 8

2의 거듭제곱

2의 거듭제곱인 수는 분해가 간단합니다:

• 16 = 2⁴
• 64 = 2⁶
• 256 = 2⁸
• 1024 = 2¹⁰

약수가 매우 많은 수

자신보다 작은 어떤 양의 정수보다도 약수의 개수가 많은 수:

• 1 (약수 1개)
• 2 (약수 2개)
• 4 (약수 3개)
• 6 (약수 4개)
• 12 (약수 6개)
• 24 (약수 8개)
• 36 (약수 9개)
• 60 (약수 12개)

인수분해의 난이도

• 작은 수: 손으로도 쉽게 분해 가능
• 큰 소수: 분해가 매우 어려움
• 세미프라임: 두 소수의 곱, RSA의 기반
• 200+자리: 고전 컴퓨터로는 현재 사실상 불가능
• 양자 컴퓨터: 쇼어 알고리즘은 효율적으로 분해 가능

자주 쓰는 분해

• 10 = 2 × 5
• 12 = 2² × 3
• 15 = 3 × 5
• 24 = 2³ × 3
• 30 = 2 × 3 × 5
• 36 = 2² × 3²
• 48 = 2⁴ × 3
• 100 = 2² × 5²
• 144 = 2⁴ × 3²
• 360 = 2³ × 3² × 5

💡 프로 팁: 작은 소수로 나누어떨어지는지 빠르게 확인하려면, 마지막 자리가 짝수면 2로, 각 자리 합이 3으로 나누어떨어지면 3으로, 마지막 자리가 0 또는 5면 5로, 각 자리 합이 9로 나누어떨어지면 9로, 교대 합이 11로 나누어떨어지면 11로 나눌 수 있습니다. 예: 4356의 자리 합은 4+3+5+6 = 18(9로 나누어떨어짐) → 4356은 9로 나누어떨어집니다! 큰 소수를 시도하기 전에 이런 빠른 체크부터 해보세요.