[알고리즘] 에라토스테네스의 체

소수 구하기 최적 알고리즘.

일반적으로 소수를 구하는 과정. 소수인지 판별할 숫자보다 작은 숫자와 하나 씩 나누는 과정에서 나머지가 없이 나누어진다면, 0과 1을 제외한 모든 숫자가 소수가 된다.

 

따라서 이 방법으로 알고리즘을 짜도 원하는 값을 얻을 수 있다. 하지만 이 방법은 상당한 시간이 걸리기 때문에, 비효율적이다.

이러한 시간 문제를 에라토스테네스의 방법으로 해결할 수 있다. 

[일일히 입력 숫자보다 작은 정수로 나누는 방법을 제외하겠다.]

[에라토스테네스의 체 개념 설명 ] 그림 출처 : 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

    start=clock();
    for(int i=2; i*i<=b; i++){
        for(int j=a; j<=b; j++){
            if(check[j]==false && i < j){
                if(j % i == 0){
                    check[j] = true;
                }
            } 
        }
    }
    end=clock();
    cout<<"걸린시간 : "<<(double)end-start<<endl;

                             [소스코드 1]

다음 [소스코드1]를 보면 각 숫자의 배수를 지우는 방법을 사용했다.

이미 체크한 숫자는 자동적으로 지나가지만, 여전히 많은 숫자를 확인해야 하므로 시간이 많이 걸린다.

이때, 생각해 볼 점이 있다. 굳이 체크할 배열을 따로 둘 필요가 없다.

시작 입력 숫자에서 끝 입력 숫자를 하나씩 대입하면서, 그 숫자를 i * i <= n 동안 비교한다면 소수인지 알 수 있다.  이 방법이 더 빠르다.

int prime(int n){
    int i;
    for (i = 2; i * i <= n; i++){
        if (n % i == 0)
            return 0;
    }
    return 1;
}

훨씬 시간이 단축된 것을 확인할 수 있다.

이상으로 에라토스테네스의 체 설명을 마치겠다.