[정수론] 에라토스테네스의 체와 소인수 분해

에라토스테네스의 체

 

 

"에라토스테네스의 체(Sieve of Eratosthenes)"는 3세기의 그리스 수학자 에라토스테네스가 정리한 소수를 찾는 방법이다.

 

n이하의 자연수에서 소수의 배수를 차례대로 소거하여 최종적으로 n이 남아있다면 n은 소수임을 알아낼 수 있다.

 

출처: 위키백과 

에라토스테네스의 체 구현에는 해당 수가 소수인지 아닌지만 저장하는 bool형의 자료구조가 필요하며, 아래 두 가지의 최적화를 거친다.

 

1. n이 인수가 있다면 인수는 √n 이하의 수와 그 이상의 수의 쌍으로 이루어지기 때문에 √n의 수까지만 확인해도 판정이 가능하다.

 

2. i의 배수를 지울때는 i*i이하의 값들은 이미 i이하의 값의 배수(ex. i*3, i*4, i*5 ... i*(i-1) 는 이미 소거)이므로 i*i이상의 값부터 소거하면 된다.

 

 

 

 

소인수 분해 알고리즘

 

 

이제 에라토스테네스의 체를 이용하여 구현하는 빠른 소인수 분해 알고리즘을 알아보자.

 

해당 알고리즘은 n의 가장 작은 소인수만을 min_factor[n]에 저장하여 소인수 분해를 구현한다.

모든 수에대하여 min_factor를 구했다면 n이 1이 될 때까지 min_factor[n]로 나누어준 값들의 min_factor들이 n의 소인수를 구성한다.

 

ex. 28(min_factor =2) -> 14(min_factor =2) -> 7(min_factor =7) -> 1(종료)

2 x 2 x 7 = 28