[Algorithm] 에라토스테네스의 체

1. 개요

 

- 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(primary number)를 찾는 방법이다. 마치 체를 치듯 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다고 함.

- 임의의 자연수 n에 대하여 그 이하의 소수를 찾는 가장 간단하고 빠른 방법.

 

2. 방법

<출처> 위키백과

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열 한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다.

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

......

위 과정을 반복하면 구간의 모든 소수가 남는다.

 

3. 구현

- C++

void Eratos(int n)
{
    /*  만일 n이 1보다 작거나 같으면 함수 종료 */
    if (n <= 1) return;

    /*	2부터 n까지 n-1개를 저장할 수 있는 배열 할당
		배열 참조 번호와 소수와 일치하도록 배열의 크기는
		n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음)	*/
	bool* PrimeArray = new bool[n + 1];

	/*  배열초기화: 처음엔 모두 소수로 보고 true값을 줌	*/
	for (int i = 2; i <= n; i++)
	    PrimeArray[i] = true;

	/*	에라토스테네스의 체에 맞게 소수를 구함
		만일, PrimeArray[i]가 true이면 i 이후의 i 배수는 약수로 i를
		가지고 있는 것이 되므로 i 이후의 i 배수에 대해 false값을 준다.
		PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
		소수가 아니게 된다. 그러므로 검사할 필요도 없다.
또한 i*k (k < i) 까지는 이미 검사되었으므로 j시작 값은 i*2에서 i*i로 개선할 수 있다.
	*/
	for (int i = 2; i * i <= n; i++)
	{
		if (PrimeArray[i])
			for (int j = i * i; j <= n; j += i)
			    PrimeArray[j] = false;
	}

	// 이후의 작업 ...
}

 

4. 응용 문제

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

1929번: 소수 구하기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    vector<int> v(m+1);
    
    v[1] = 1; // 1은 소수가 아니므로 체크.
    for(int i = 2; i <= m; i++) {
        for(int j = 2 * i; j <= m; j = j+i) { // i를 곱해줌으로서 자기자신은 체크하지 않음.
            v[j] = 1; // 체크된 수들은 소수가 아님.
        }
    }
    
    for(int i = n; i <= m; i++) {
        if(v[i] == 0) cout << i << '\n';
    }
}

 

 

출처 : 위키백과, 백준