백준 4948번 C언어 풀이

참 오랜만에 백준을 푼 것 같다.

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

베르트랑 공준에 관한 문제. 임의의 자연수 n에 대해 n ~ 2n사이에 소수는 적어도 하나가 존재한다는 이론이다. 현재 완전히 증명되어있는 이론.

 

소수문제를 풀면서 에라토스테네스의 체를 한번 구현해 놓으니 거의 모든 소수문제가 복붙수준으로 풀리고 있다.

 

이 문제도 에라토스테네스의 체를 한번 만들어 놓은 후에, 범위에 따라 개수를 세면 되는 문제.

#include <stdio.h>
#define MAX_SIZE 123456 * 2 + 1

int main () {
    int seive[MAX_SIZE] = {0,};
    for (int i = 2; i < MAX_SIZE; i++) {
        seive[i] = 1; 
    }
    for (int i = 2; i < MAX_SIZE; i++) {
        if (seive[i]) { 
            for (int p = 2; i*p < MAX_SIZE; p++) {
                seive[i*p] = 0;
            }
        }
    }
    
    int n = 1;
    int cnt = 0;
    while (1) {
        cnt = 0;
        scanf("%d", &n);
        if (!n) break; //n이 0이면 break

        for (int i = n + 1; i <= 2 * n; i++) {
            if (seive[i]) cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}