[알고리즘] 에라토스테네스의 체 (소수 구하기)

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

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

 

에라토스테네스의 체는 소수를 구하는 방법이다.

 

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

	bool* PrimeArray = new bool[n + 1];
    
	for (int i = 2; i <= n; i++)
	    PrimeArray[i] = true;

 

Eratos 함수는 n 이하의 소수들을 구한다. 

먼저 n+1 크기 만큼의 동적 배열을 만들고 값을 모두 true로 초기화한다. (모두 소수라고 가정)

 

    for (int i = 2; i * i <= n; i++)
    {
        if (PrimeArray[i])
            for (int j = i * 2; j <= n; j += i)
                PrimeArray[j] = false;
    }
    /* for (int j = i * i; j <= n; j += i)
                PrimeArray[j] = false; 
    j 초기값을 i*i로 시작해서 개선할 수도 있다고 하는데 왜 되는지 모르겠음 */

 

그리고 PrimeArray[i]가 true인 값들의 배수들을 모두 false로 설정해 소수가 아니게 설정한다.

위키피디아에서는 i*k(k<i) 까지 소수 검사가 완료되어 j=i*i로 시작해도 된다고 하는데 왜 되는지 아직 모르겠다.

이러면 일단 끝이다. 간단한 알고리즘이다.