백준 4948 : 베르트랑 공준

오늘부턴 풀이도 같이 써보겠다.

 

우선, 소수를 구하는 방법은 이전 에라토스테네스의 체를 사용하겠습니다.

https://namu.wiki/w/에라토스테네스의%20체

에라토스테네스의 체에 대한 문서입니다. 참고하시면 되겠습니다

간단하게 요약하자면, 2~N까지의 수를 놓습니다. 그리고 여기서 지워지지 않은 수 중 가장 작은 수는 소수입니다. 그리고 그 소수의 배수를 모두 지웁니다, 이 과정을 반복하면 결과적으로 소수만 남게됩니다.

 

이전 문제에서 에라토스테네스의 체를 구현하여 소수 구하는 방법을 써놨으니 그 코드를 이용하면 됩니다.

범위만 정해주면 되는 문제이기때문에 사실상 문제의 핵심은 '에라토스테네스의 체'의 구현입니다.

 

#include <stdio.h>

int solve() {
    int M = 1, N, res[1000000], cnt = 0;
    while(M != 0) {
        scanf("%d", &M);
        N = 2 * M;

        for(int i=0;i<=N;i++)
            res[i] = i;

        for(int i=2;i<=N;i++) {
            if(res[i] == 0)
                continue;
            for(int j=i*2;j<=N;j+=i) 
                res[j] = 0;
        }

        for(int i=M;i<=N;i++) {
            if(res[i] != 0 && res[i] != 1 && res[i] > M)
                cnt++;
        }

        if(cnt != 0)
            printf("%d\n", cnt);

        cnt = 0;
    }
}
 
int main() {
    solve();
    return 0; 
}