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

자연수 A가 $A=a^m\ast 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 (개) 이다