5.4 예제 프로그램 - 에라토스테네스의 체

[광룡]

이절에서 설명할 예제는 '에라토스테네스의 체'라고 하는 솟수를 찾는데 사용하는 아주 전통적인 알고리즘이다(제 또래 분들은 아마 예전 중학교 수학 시간에 배웠을 것임). 일단 솟수를 찾고자 하는 범위까지의 수들을 정수 vector에 담기로 한다. 이 알고리즘의 아이디어는 소수가 될 수 없는 수들을 하나씩 지워 나가면 (0으로 세팅), 가장 마지막에 남는 수들이 솟수가 된다는 것이다. 이를 위해서는 루프를 돌면서 각각의 값들이 1로 세팅된 수들의 배수인 것들을 하나씩 지워나가면 된다. 바깥쪽 루프가 끝나면 남아있는 수들이 솟수가 되는 것이다. 이 알고리즘의 프로그램은 다음과 같다.

int main()
{
   // 각 숫자들을 1로 모두 세팅한다.
   const int sievesize = 100;
   vector<int> sieve(sievesize, 1);

   // 1로 세팅된 값들 각각에 대해 이 수의 배수들을 0으로 세팅한다.
   for (int i = 2; i * i < sievesize; i++)
      if (sieve[i])
         for (int j = i + i; j < sievesize; j += i)
            sieve[j] = 0;

   // 1로 세팅된 숫자들만 출력한다.
   for (int j = 2; j < sievesize; j++)
      if (sieve[j])
         cout << j << " ";
   cout << endl;
}