에라토스테네스의 체 - 소수 구하기

먼저 소수(Prime Number)에 대해 이해하고 넘어가야겠다.

소수는 1을 제외한 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

즉, 13은 1 X 13 말고는 성립하는 식이 없기 때문에 소수이다.

 

이 소수를 구하는 가장 최적화된 방법으로 알려진 것이 바로 에라토스테네스의 체이다.

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수 판정법이다.

 

쉽고 빠른 이해를 위해 간단한 예시와 함께 알아보자.

 

Q) 120까지의 자연수 중 소수를 구하라.

 

 알고리즘은 아주 간단하다.

2부터 120까지 순차적으로 탐색하며 자신의 1,2,3..... 배인 수들을 삭제한다.

이때 이미 삭제된 숫자는 탐색할 필요가 없다.

즉, 아래 그램처럼 탐색 순서는 2,3,5,7,11..... 순으로 나아간다.

출처: wiki

눈치가 빠른 사람이라면 여기서 특이한 점을 발견할 수 있다.

11부터는 더이상 삭제할 숫자가 남아있지 않는 것이다.

11^2 = 121 > 120이다.

 

결과적으로 도출해낼 수 있는 아이디어는 주어진 N의 제곱근 √N까지만 탐색을 진행하면

남아있는 모든 수들은 '소수'라는 것이다.

 

아래는 에라토스테네스의 체를 구현하는 핵심코드이다.

int[] eratos = new int[N+1];

for(int i=2 ; i<=Math.sqrt(N) ; i++) {
  int tmp = i*2;
  while(tmp <= N) {
    eratos[tmp] = 1;
    tmp += i;
  }
}