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

에라토스테네스의 체(Sieve of Eratosthenes)

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 고안한 소수 판별 알고리즘이다.

이 알고리즘은 2부터 시작하여 특정 숫자의 배수를 지워 나가는 방식으로 소수를 찾는다.

---

작동 원리

출처: 나무위키

 

1. 2부터 N까지의 모든 정수를 나열한다. 
2. 나열된 정수 중 남아 있는 가장 작은 숫자를 찾고, 이를 소수로 마킹한다.
3. 이 숫자의 배수들을 모두 리스트에서 제거한다.
4. 리스트에 남아 있는 숫자 중 가장 작은 수를 찾아 위의 과정을 반복한다.
5. 리스트에 더 이상 제거할 수가 없을 때까지 반복한다.

---

구현 in C++

#include <iostream>
using namespace std;
//2~1000까지 소수를 찾아 테이블에 마킹한다
#define MAX 1000
bool table[MAX+1];

int main()
{
    //조건문 i*i
    for (long long i = 2; i * i <= MAX; i++)
    {
        if (!table[i])
        {
            for (long long j = i * i; j <= MAX; j += i)
            {
                table[j] = 1;
            }
        }
    }

    for (long long i = 2; i < MAX; i++)
    {
        if (!table[i])
        {
            cout << i << " ";
        }
    }

    return 0;
}

 

• 위 코드는 i*i를 조건부에 사용한다. 에라토스테네스의 체에서 반복문의 조건에 i * i를 넣는 이유는 효율성을 높이고 불필요한 계산을 줄이기 위해서이다.
• 예를 들어, 숫자 n에 대해 모든 배수를 지우는 작업을 할 때, 숫자 i의 배수 i * k(여기서 k는 i보다 큰 어떤 수)의 경우 이미 이전 단계에서 처리되었다. (ex: i = 3일 때 3 * 2 = 6과 같은 수는 이미 i = 2일 때 처리되었다.)
• 따라서 i의 배수를 지우는 작업을 할 때, i가 커질수록 더 많은 수가 이미 지워져 중복 처리가 발생한다. 이를 피하기 위해 i * i까지의 배수들만 처리하면 충분하다.

---

문제 추천

https://www.acmicpc.net/problem/1929

https://www.acmicpc.net/problem/4948

https://www.acmicpc.net/problem/2960

https://www.acmicpc.net/problem/17103

https://www.acmicpc.net/problem/1153