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

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

 

1부터 N사이의 모든 소수와 소수가 아닌 수를 찾는 방법이다.

 

소수는 1과 자기 자신만을 약수로 가지는 수이다.

 

쉽게 말해 소수는 자기 자신과 1로 밖에 못 나누는 수이다.

 

이러한 원리를 이용해 배수를 지우면서 소수가 아닌 수를 배제해 나가는 방법이다.

 

즉, 

 

1)---

2의 배수인 4, 6, 8, 10, 12..........지움 

3의 배수이면서 지워지지 않은 수인 9, 15, 21.......지움

.

.

.

.

.

.

2)---

이러한 과정을 반복하며 소수가 아닌 수를 지워나간 후

 

마지막까지 지워지지 않은 수인 소수를 찾는 방법이다.

 

-----

 

예를 들어 1 ~ 50 사이의 소수를 찾는 다면,

 

 

1은 소수가 아니므로 먼저 배제하고

 

2의 배수들을 배제한다.

 

 

다음으로, 2의 배수들을 배제하고 남은 수들 중 3의 배수들을 소거해 나간다.

 

 

그 다음으로, 5의 배수

 

 

마지막으로 7의 배수를 소거한다.

 

 

이렇게 되면 1 ~ 50 사이에서 소수는 칠해진 숫자들이다.

 

아래는 위 알고리즘을 이용하여 2 ~ N까지의 소수를 출력하는 코드이다.

------------------------------------------------------------------------------

 

#include <stdio.h>
 
#define MAX 10001
 
int N;
int arr[MAX];
 
void Eratosthenes()
{
    arr[1] = 1;
 
    for(int i = 2; i <= N;++i)
    {
        if (arr[i])
            continue;
 
        for (int j = i + i; j <= N; j += i)
            arr[j] = 1;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    Eratosthenes();
 
    for (int i = 0; i < N; ++i)
    {
        if (!arr[i])
            printf("%d ", arr[i]);
    }
 
    return 0;
}