본문 바로가기
Dev Talks/Algorithm

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

by 곰씨네IT 2017. 3. 22.
** 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)까지의 숫자로 나누는 작업을 반복



** 큰사각형 광고 **



댓글