[C++] 에라토스테네스의 체

백준 1929번 / 소수 구하기 / C++

백준 1929번, 소수 구하기 문제에서 효율적인 풀이방식으로 에라토스테네스의 체 알고리즘을 사용한다.

---

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

큰 범위에서 각 자연수를 일일이 소수인지 판별하는과정은 매우 무겁기때문에, 에라토스테네스의 체 알고리즘을 이용하여 빠르게 큰 범위의 자연수의 각각이 소수인지 판별한다.

 

#include <stdio.h>
#include <math.h>

int main()
{
    //에라토스테네스의 체에서 사용할 소수 판별을 할 배열
    bool* flag;

    //최소부터 최대까지 주어진 경우 입력하는 변수
    int m, n;

    //값 입력
    scanf_s("%d %d", &m, &n);

    //최대값까지 동적할당을통해 배열을 만든다.
    //new bool[]()로 Zero-initialized를 통해 false인 상태로 생성할 수 있다.
    //관련 주소 https://stackoverflow.com/questions/4262914/set-default-value-of-dynamic-array
    //이렇게 구현한 이유는 true로 시작할 수 있지만, O(n) 시간 복잡도로 굳이 true로 바꿔
    //불필요한 처리를 하는것이 비효율적이라 판단하였다.
    flag = new bool[n + 1]();

    //1은 소수가 아니다 -> 참으로 바꿔 출력되지 않게한다.
    flag[1] = true;

    //소수를 찾는데 최대값의 제곱근까지 검사한다.
    for (int i = 2; i <= sqrt(n); ++i)
    {
        //i가 소수인가?
        if(!flag[i])
        {
            //i에 n배는 모두 소수가 아니므로 true로 바꿔준다.
            for (int j = i * 2; j <= n; j += i)
            {
                flag[j] = true;
            }
        }
    }

    //true가 아닌 모든 값들이 소수가 아닌것으로 나타난다.
    for (int i = m; i <= n; ++i)
    {
        if (!flag[i]) printf("%d\n", i);
    }
}

 

flag = new bool[n + 1]();

• m부터 n까지 범위가 주어지면, n+1까지의 boolean 변수를 동적할당한다. +1를 한 이유는 가독성을 올리기 위해 index 자체가 자연수num이 되도록 하기 위해서이다.

 

for (int i = 2; i <= sqrt(n); ++i)

• 2부터 n의 제곱근까지 반복하여 수행한다. 제곱근까지 하는 이유는 소수를 판별할 때, 제곱근을 기준으로 약수의 반전이 일어나 제곱근보다 큰 수를 검사할 필요가 없다.

 

if(!flag[i])

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

• !flag[i] 조건이 참이되면 i를 제외한 배수는 모두 소수가 아니다. 이유는 i와 특정 값을 곱할 수 있기 때문. 모두 true로 소수가 아니라고 결정짓는다.