에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수 구하기 알고리즘이다.

 

알고리즘

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (위는 120까지가 예시)
2. 짝수 중 유일하게 2는 소수이므로 2는 소수로 체크해준다. (빨간색)
3. 2를 제외한 2의 배수를 모두 지워준다.
4. 3은 소수이므로 3은 소수로 체크해준다.(초록색)
5. 3을 제외한 3의 배수를 모두 지워준다.
6. 5는 소수이므로 5는 소수로 체크해준다.(파란색)
7. 5를 제외한 5의 배수를 모두 지워준다.
8. ... 3~4단계의 과정을 소수를 만날때마다 해주면된다.

간단하게 말해서, 본인이 설정한 범위의 최댓값을 x라고 한다면,

2부터 시작해서 x까지 소수의 배수를 다 지워버리면 된다.

 

코드(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;
	}

	// 이후의 작업 ...
}

 

주석중에 i*k 까지는 이미 검사되었으므로 j시작 값은 i*2에서 i*i로 개선할 수 있다. 라는 부분이있다.

이 문장을 예시를 들어 설명하자면,

 

예를들어 i가 5가 되기 이전까지 이미 반복문을 완료했다면, 앞의 2,3,4에서 2*5, 3*5, 4*5까지 모두 완료했을 것이다.

따라서 5*5부터 즉, i*i부터 하면 된다는 말이다.

 

그리고 배열 초기화 부분에서 모두 true로 초기화 하게 되는데,

반복문으로 모두 초기화하는 방법도 있지만,

fill_n(PrimeArray, n+1, true);

fill_n(초기화할 배열 이름, 범위, 초기화 할 값)으로 초기화가 가능하다.