[알고리즘 #5] 소인수분해(prime factorization) 알고리즘 정리

** Responsive Ad **

1. 소인수 (prime factor)

어떤 N을 구성하는 인수 중에 소수인 것

2. 소인수 분해 (prime factorization)

소수를 이용하여 어떤 수 N을 만드는 곱의 형태로 표현한 것 

ex) 20을 소인수 분해하면 2 x 2 x 5 로 20의 소인수는 2, 5이다.

3. 어떤 수 N에 대한 소인수 분해 알고리즘

1) N을 2부터 sqrt(N) 까지 차례대로 나누어 나머지가 0인지 검사 -> 나머지가 0인 수가 나오면 그 몫을 다시 N으로 하여 2부터 sqrt(N)까지의 숫자로 나누는 작업을 반복

** 큰사각형 광고 **