4948번: 베르트랑 공준

#include <cstdio>

using namespace std;

#define max 246912

int main()

{

int n, count;

bool num[246913];

for (int i = 0; i <= max; ++i)

num[i] = 1;

for (int i = 4; i <= max; i += 2)

num[i] = 0;

for (int i = 3; i*i <= max; i += 2)

if (num[i] == 1)

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

num[j] = 0;

for (scanf("%d", &n), count = 0; n; count = 0, scanf("%d",&n))

{

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

(num[i] == 1) ? ++count : count;

printf("%d\n", count);

}

}