ACM-ICPC 2011年 国内予選 問題A チェビシェフの定理

問題A:チェビシェフの定理

エラトステネスの篩を用いて、素数表を作るだけの問題。2006年国内予選の問題Aも素数表を使う問題だったが、今回の方が簡単。

実際に提出したコードではなく、清書したものなので、確認した入力はサンプルインプットのみ。確認済。

#include <iostream>
#include <cstring>
using namespace std;

int n;

#define MAX 300000
char primes[MAX];

void e()
{
    memset(primes, 1, sizeof(primes));
    primes[1] = 0;
    for (int i = 2; i < MAX; i++)
        for (int j = 2*i; j < MAX; j += i)
            primes[j] = 0;
}

int main()
{
    e();
    while (cin >> n, n) {
        int ans = 0;
        for (int p = n+1; p <= 2*n; p++)
            if (primes[p])
                ans++;
        cout << ans << endl;
    }
    return 0;
}