에라토스테네스의 체

자바 소수판별 알고리즘을 공부하다보니 에라토스테네스의 체에 관련된 알고리즘을 보고 공부를 하게 되었다.

코딩테스트를 위해 클린코드를 지향하는 나로서 매우 중요한 부분인거 같아서 정리해보고자 한다.

 

에라토스테네스의 체는 N이하의 수들이 소수인지 아닌지 판별할 때, n(임의의 수)의 배수들을 모두 지움으로써 시간복잡도를 저하시킨다는 장점을 가지고 있다.

 

아래의 코드를 직접 살펴보며 공부하도록 하자 

 

예시로 N을 16이라고 해보자.

배열은 index값이 0,1,2....16까지 있는 17의 크기를 가진 Boolean타입의 배열이 생성되었을 것이다. 

16의 제곱근 값은 4가 되고, 

i=2, i<4, i++된다는 조건하에 

j = 4가 될 것이고, j는 i.즉 2씩 더해주게 되며 

prime[j]값은 true 즉 소수가 아닌 것이 된다. 

이렇게 i씩 증가시킨다는 것은 결국 배수를 모두 소수로부터 제외시키게 되는 것이다

i=3 일 때도 마찬가지로 같은 알고리즘을 통해 3의 배수들을 모두 지우게 된다