소인수분해를 이용한 약수 구하기

자연수 A가 \( A=a^m*b^n \) 로 소인수분해될 때,

 

1. 자연수 A의 약수 : \( a^m \) 의 약수와 \( b^n \) 의 약수를 곱하여 구할 수 있다

 ex)
12를 소인수분해 하면 \( 2^2 \) * 3 이므로 \( 2^2 \) 의 약수 1, 2, 4와 3의 약수 1, 3의 곱으로 구할 수 있다

 

2. 자연수 A의 약수의 개수 : (m+1) * (n+1) (개)

 ex)
12 = \( 2^2 \) * 3 이므로 12의 약수의 개수는 (2+1) * (1+1) = 6 (개) 이다
32 = \(2^5 \) 이므로 32의 약수의 개수는 (5+1) = 6 (개) 이다