에라토스테네스의 체(Eratosthenes' sieve)

에라토스테네스의 체(Eratosthenes' sieve)

1부터 N까지 범위 안에 들어가는 모든 소수를 구하기 위해서는 에라토스테네스의 체를 이용한다.

- Algorithm -

 

1. 2부터 N까지 모든 수를 쓴다.

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

3. 그 수를 지우고 소수로 저장한다.

4. 이제 그 수의 배수를 모두 지운다.

예를들면 N이 20이라 생각해보자.

-1-(2부터 N까지 모든 수를 쓴다.)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

-2-(아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

-3-(그 수를 지우고 소수로 저장한다. 여기서는 빨간색을 모두 저장했다고 가정한다.) 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

-4-(이제 그 수의 배수를 모두 지운다.)

2 3 5 7 9 11 13 15 17 19

-5-(아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.) 

2 3 5 7 9 11 13 15 17 19

-6-(그 수를 지우고 소수로 저장한다. 여기서는 빨간색을 모두 저장했다고 가정한다.) 

2 3 5 7 9 11 13 15 17 19

-7-(이제 그 수의 배수를 모두 지운다.)

2 3 5 7 11 13 17 19

-8-(아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.) 

2 3 5 7 11 13 17 19

-9-(그 수를 지우고 소수로 저장한다. 여기서는 빨간색을 모두 저장했다고 가정한다.) 

2 3 5 7 11 13 17 19

-10-(이제 그 수의 배수를 모두 지운다.)

2 3 5 7 11 13 17 19

...

2 3 5 7 11 13 17 19

이렇게 최종적으로는 2, 3, 5, 7, 11, 13, 17, 19가 에레토스테네스의 체에 의해 걸러지게 된다.

소스 코드는 아래와 같다.

MAX는 자신이 에라토스트테네스의 체를 통해 몇 번째 수까지 소수를 구할지 생각하여 기입하면 된다.

이 코드를 이용하여 풀 수 있는 문제는 다음과 같다.

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

#include <iostream>
#include <cstdio>
#define MAX 1001
using namespace std;
 
int arr[1002];
 
/*
에라토스테네스의 체
Sieve of Eratosthenes
- 1부터 N까지 범위 안에 들어가는 모든 소수를 구하기 위해 에라토스테네스의 체를 이용한다.
1. 2부터 N까지 모든 수를 쓴다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3. 그 수를 지우고 소수로 저장한다.
4. 이제 그 수의 배수를 모두 지운다.
*/
 
void Eratosthenes(int num)
{
    int i;
    //2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
    for (i = 2; i <= num; i++)
    {
        if (arr[i] != 0 && arr[i] != -1)
            break;
        else if (i == num)
            return;
    }
    // 3. 그 수를 지우고 소수로 저장한다.
    // (여기서는 0로 변환된 것이 소수, -1으로 변환된 것이 지워진 것)    
    arr[i] = 0;
 
    // 4. 이제 그 수의 배수를 모두 지운다.
    for (int j = 2; i*j <= num; j++)
        arr[i*j] = -1;
 
    Eratosthenes(num);
    return;
}
int main()
{
    int n, cnt = 0;
    scanf("%d", &n);
    
    //1. 2부터 N까지 모든 수를 쓴다.
    for (int i = 2; i <= MAX; i++)
        arr[i] = i;
 
    Eratosthenes(MAX);
 
    arr[1] = -1; // 1은 소수가 아니다.
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        // arr[val]값이 소수냐?
        arr[val] == 0 ? cnt++ : 0;
    }
 
    printf("%d", cnt);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>