에라토스테네스의 체 알고리즘

에라토스테네스의 체 알고리즘

소수를 구하는 대표적인 판별법

 

* 소수(Prime Number) : 1과 자기 자신 외에 약수가 존재하지 않는 수

    ⇒ 1은 소수가 아니다.

 

• 시간 복잡도 : O(Nlog(logN))

+ 매우 빠르게 동작한다.

- 메모리가 많이 필요하다.

  ⇒ 알고리즘을 수행할 때 N의 크기만큼 배열을 할당해야 하기 때문

 

 

에라토스테네스의 체 핵심 이론

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

[ 예시 ]

 

[ 예시 ]

1부터 30까지의 모든 자연수를 나열한다.

 

2. 2부터 시작하고, 남은 수 중에서 지워진 상태가 아닌 가장 작은 수를 찾는다.

 

3. 남은 수 중에서 현재 선택된 숫자의 배수를 배열에서 끝까지 탐색하면서 제거한다. 이때 처음으로 선택된 숫자는 제거하지 않는다.

[ 예시 ]

 

[ 예시 ]

2를 제외한 2의 배수를 모두 제거한다.

 

4. 배열의 끝까지 2번과 3번의 과정을 반복한다.

[ 예시 ]

 

[ 예시 ]

1부터 30까지의 모든 소수 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

 

 

에라토스테네스의 체 구현

for(int i = 2; i <= N; i++)
{
  A[i] = i;
}
for(int i = 2; i <= sqrt(N); i++)
{
  if(A[i] == 0)
  {
    continue;
  }
  for(int j = i + i; j <= N; j = j + i)
  {
    A[j] = 0;
  }
}

• N의 제곱근까지만 탐색하는 이유 : N의 제곱근이 n일 때, N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가지기 때문이다.

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>을 참고하였습니다.