백준 4948번

BOJ 4948 : 베르트랑 공준

백준 > 단계별로 풀어보기 > 수학 2 의 소수 관련 문제들은 전부 에라토스테네스의 체를 응용하면 쉽게 답을 구할 수 있다. 베르트랑 공준 역시 마찬가지이다. n의 값에 따라 알맞게 범위를 생성하고, 범위 내의 소수를 에라토스테네스의 체를 이용해 구분해낸다.

#include <stdio.h>

int main()
{
    int n;

    char non_prime[1000000] = { 0, };

    while(1)
    {
        while(scanf("%d", &n) != 1) continue;

        if (n == 0)
            break;
        
        for (int j = 2; j <= 2 * n; j++)
        {
            for (int t = 2; t * j <= 2 * n; t++)
            {
                if (non_prime[t * j] != 1)
                    non_prime[t * j] = 1;
            }
        }

        non_prime[0] = non_prime[1] = 1;

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