[알고리즘] 에라토스테네스의 체 : 소수 판별법

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

이 방식은 지정됨 범위네에서 대량의 소수를 한번에 구할때 유용하다.

예를 들어 121 이하의 소수를 모두 구해야 한다고 해보자. 어떻게 해결해야 할까?

 

결론부터 말하면 121의 제곱근, 즉 11 이하의 소수 n에 대하여 n의 배수들은 전부 제외시키면 된다. 

n의 배수라는 말 자체가 소수가 아니다.

 

아직 이해가 잘 안갈 수 있다. 다시 설명해 보자.

 

121의 제곱근인 11이하의 수 들을 생각해보자.

 

일단 2는 소수니 제거하지 않는다.

2를 제외한 모든 2의 배수 4, 6, 8, 10, ..., 120 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다.

3를 제외한 모든 3의 배수 6, 9, 12, ... 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다.

4는 아까 2의 배수에서 제거 됬으니 소수가 아니다.

5를 제외한 모든 5의 배수 5, 10, 15, ... 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다.

 

이를 그림을 통하여 확인해 보자.

 

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;
	}

	// 이후의 작업 ...
}

 

출처는 위키피디아 참고

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전