[C++] 최적의 소수찾기, 에라토스테네스의 체

안녕하세요 강민성입니다.

이번 포스팅에서는 소수를 찾는 방법에 대해서 알아보도록 하겠습니다.

소수를 찾는 방법이 여러가지가 있지만 그 중에 가장 효율이 좋은

'에라토스테네스의 체' 에 대해서 알아보도록 합시다.

최적의 소수 찾기, 에라토스테네스의 체

먼저 동영상을 보고 어떠한 원리로 소수를 찾는지 보도록 하겠습니다.

2부터 120까지 수 중 소수를 판별한다고 해보겠습니다.

다음과 같은 알고리즘으로 소수를 찾게 됩니다.

1. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수들은 소수가 아니므로 체크한다.

2. 다음 숫자를 확인하여 체크가 안되있으면 그 수를 오른쪽에 쓰고 그 수의 배수들은 체크,

체크가 되어있으면 다음 수로 넘어간다.

3. 120의 제곱근까지 다음 과정을 반복한다.

이 알고리즘을 이제 C++ 언어로 구현해보겠습니다.

#include <iostream>
#include <math.h>
 
// 에라토스테네스의 체
#define SIZE 100
int arr[SIZE+1];
 
int main(int argc, const char *argv[])
{
    int i,j;
    
    // 배열 초기화
    for(i=2;i<=SIZE;i++){
        arr[i] = i;
    }
    
    for (i=2;i<=sqrt(SIZE);i++){
        // 이미 체크된 수의 배수들은 합성수임이 자명
        if(arr[i] == 0)
            continue;
        // i를 제외한 i의 배수들을 0으로 체크
        for (j=i+i;j<=SIZE;j+=i){
            arr[j] = 0;
        }
    }
    
    int count = 0;
    for(i=2;i<=SIZE;i++){
        if (arr[i]!=0){
            std::cout.width(3);
            std::cout << arr[i];
            // 5개씩 출력하기 위한 
            count++;
            if (count % 5== 0)
                std::cout << std::endl;
        }       
    }
}

마무리

개인적으로 이름이 너무 어렵다고 생각합니다..

이 방식으로 소수를 구하지 않으면 시간복잡도에 걸리는 문제가 많아,

프로그래밍 언어로는 몇 번 구현을 해보았지만

 아직도 이름이 헷갈려서 이번 포스팅 때도 이름을 다시 찾아보았습니다.

여러분은 특이한 이름이니만큼 잘 기억해두셨다가 요긴하게 쓰셨으면 좋겠습니다.