에라토스테네스의 체

에라토스테네스의 체란?

에라토스테네스의 체는 소수를 찾는 방법 중 하나이다. 고대 그리스 수학자 에라토스테네스가 발견했다.

원리

위 그림과 같이 동작하는데, 정리를 해보면 다음과 같다.

 

1. 2의 배수부터 시작한다고 했을때 2 * 2부터 구하려는 범위(여기서는 120)까지 2의 배수가 있으면 걸러낸다.

2. 작업1 을 n^2 > m (m : 소수를 구하려는 범위)을 만족하는 n의 배수까지 반복한다. (여기서는 120이기 때문에 11^2 > 120을 만족하므로 n은 11이다)

3. 그리고 걸러내지 않은 나머지 값들이 소수가 된다.

구현

구현 코드는 다음과 같다.

void Eratos(int m) {
    // 만약 m이 1보다 작거나 같으면 함수 종료 
    if(m <= 1) return;
    
    // 2부터 m까지 n-1개를 저장할 수 있는 배열을 할당한다.
    // 인덱스 번호와 소수가 일치하도록 배열의 크기는
    // m + 1 길이만큼 할당한다. (인덱스 0, 1은 사용안함)
    bool* primeArray = new bool[m + 1]; 
    
   	// 배열 초기화
    for(int i = 2; i <= m; ++i)
        primeArray[i] = true;
    
    // 만약 PrimeArray[i]가 true이면 n이후의 n배수는 약수로 n을 
    // 가지고 있는 것이 되무로 n 이후의 배수에 대해 false값을 준다.
    // primeArray[i]가 false이면 i는 이미 소수가 아니다.
    for(int n = 2; n * n <= m; ++n) {
        if(primeArray[i]) {
            for(int i = n * n; i <= m; i += n) 
                primeArray[i] = false;
        }
    }
    
    // 이후 작업
}