에라토스테네스의 체 (소수 구하기)

에라토스테네스의 체

소수를 찾는 가장 기본적인 알고리즘이다.

소수를 찾고 싶은 범위 전체에서 소수가 아닌 수를 지워나가는 방법이다.

우선 소수를 찾을 범위 만큼의 배열을 생성하고 0으로 초기화 한다. .

std::vector<int> (end-start + 1 , 0);

배열 내의 모든 요소에 대해 다음을 반복한다.

2부터 현재 요소-1까지의 모든 수로 현재 요소를 나눈다.

나머지가 0인 경우 소수가 아니다. (1과 자기 자신 외에 다른 약수가 있기 때문에)

소수가 아닌 경우 해당 인덱스의 값을 1 증가시킨다.

소수인 경우 넘어간다.

해당 과정을 반복하면 배열에서 값이 0인 인덱스는 소수가 된다 .

코드로 나타내면 다음과 같다.

for(int i=num1; i<= num2; i++){ 
        for(int j = 2; j < i ; j++){
            if(i%j==0){
               all_num[i-num1] = 1; 
               break;
            }
        }
    }

이 방법의 문제는, 시간복잡도 면에서 너무 좋지 않다는 것이다.

이 때, 두 가지 방법을 사용해 시간복잡도를 개선할 수 있다.

첫 번째는 이미 지운 숫자에 대해서는 검사하지 않고 넘어가는 방법이다.

현재 구현에서는 배열의 요소가 0인 경우에만 검사를 수행함으로써 이미 소수가 아닌 것으로 판별이 난 경우는 건너뛸 수 있다.

두 번째 경우는 제곱근을 이용하는 방법이다.

N의 약수가 존재한다면, 반드시 sqrt(N)의 범위에 존재한다.

어떤 수가 소수가 아니라면, 두 수의 곱으로 나타낼 수 있다.

n = a * b

이 때, sqrt(n) * sqrt(n) = n 이기 때문에 a 와 b 는 동시에 sqrt(n)보다 클 수 없다.

즉, 둘 중 하나는 반드시 sqrt(n) 보다 작다.

따라서 특정 수의 제곱근까지만 검색해보면 해당 수가 다른 약수를 가지는 지 아닌지, 즉 소수인지 아닌지를 판단할 수 있다.

이렇게 두 가지 방법을 사용하면 시간복잡도를 줄일 수 있다.

에라토스테네스의 체 알고리즘의 시간 복잡도에 대한 자세한 설명은 다음을 참고하면 쉽게 이해할 수 있다.

Time complexity of Sieve of Eratosthenes algorithm

두 가지 방법을 적용한 코드는 다음과 같다.

vector<int> all_num(num2-num1+1,0);

    for(int i=num1; i<= num2; i++){ 
        if(all_num[i-num1]==0){
        for(int j = 2; j <= sqrt(i) ; j++){
            if(i%j==0){
               all_num[i-num1] = 1; 
               break;
            }
         }
        }
    }