에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방식이다.

bool prime_number(int num) {
    if (num < 2) return false;
    int a = (int)sqrt(num);
    for (int i = 2; i <= a; i++)
        if (num % i == 0) return false;
    return true;
}일반적으로 소수 찾는 알고리즘으로 어떤 num이라는 숫자가 들어오면

2부터 num의 제곱근까지 1씩증가시키면서 나눠본다. 나눠보고 나머지가 0이면 

현재 계산중인 숫자로 나눠진다는 말이기때문에 소수가 아니다.

 

제곱근까지만 나누는 이유는 2는 제곱하면 4가되고 4는 16이 됌으로 

만약 4까지 소수인지 구하고 싶다면 2까지만 계산해보면된다.

이것은 시간복잡도 O(N^1/2)로 괜찮은 편이다.

ㅇ근데 만약 대량의 숫자를 판별해야한다면? 시간복잡도가 N N^1/2로 올라간다.

 

이를 개선하기 위해서 한번에 대량의 소수를 구하기 위해 에라토스테네스의 체를 이용한다.

위의 그림에서 보듯 2부터 자신을 제외한 자신의 배수들을 모두 체크한다. 

이것을 N의 제곱근 즉 , sqrt(N)까지 반복하는 것이다. 코드는

 

int a[사이즈만큼]={0};

 

for(int i =2; i<=sqrt(N); i++){

    if(a[j]==0){//소수만 체크하면서 돌 수 있도록

       for(int j =2; i * j<size; j++){

        a[i*j]=true;

    }

  }

}

이렇게하면 소수가 아닌 수들이 모두 체크가 된다.