[C/C++] 백준 #1929 소수 구하기(에라토스테네스의 체)

주어진 범위안의 숫자에 대해서 소수를 출력하라는 문제입니다.

 

사실 소수 구하기는 여러가지 방법이 있지만, 에라토스테네스의 체를 사용하는 것이 가장 빠른 편입니다.

 

Eratosthenes' sieve

 

에라토스테네스의 체를 사용하는 데 있어서 단점은 처음부터 해야한다는 것입니다.  특히 2의 배수의 개수는 많으므로, 보다 효율적인 형태를 만들려면, m이 2보다 작거나 같고, n이 2보다 크거나 같으면, 2는 무조건 출력하고, 홀수에 대해서만 처리하는 방법입니다.  그렇게 하면 전체적으로 \(\frac{1}{4}\)로 줄일 수 있습니다.  또한 메모리 문제입니다.  메모리 제한이 작으면, 에라토스테네스의 체를 비트필드 형태로 하든지 아니면, \(n \sqrt{n}\) 알고리즘으로 만들어야 합니다.

 

이 문제 자체가 Silver III 등급정도의 문제로 굳이 복잡하게 짤 필요는 없습니다.  그래서 그냥 보편적인 형태의 에라토스테네스의 체를 사용했습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------
//    baekjoon #1929 Prime Numbers
//        - by Aubrey Choi
//        - created at 2020-01-13
//------------------------------------------------
#include <stdio.h>

static char e[1000004];
int main()
{
    int m, n, i, j;
    scanf("%d%d", &m, &n);
    for(i=2;i<=n;i++)
    {
        if(e[i]) continue;
        if(i>=m) printf("%d\n", i);
        if(i<1000) for(j=i*i;j<=n;j+=i) e[j]=1;
    }
}