AOJ Volume11 1172: Chebyshev's Theorem

エラトステネスの篩で素数テーブルを作成しておく。

 /************************
* 2012/06/30                     *
* AOJ Volume11 1172        *
* Chebyshev's Theorem    *
* crane                             *
*************************/


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

#define MAX_N 246913

bool field[MAX_N];

int main(){

    field[0] = false;
    field[1] = false;
    for(int i=2; i<MAX_N; i++)    field[i] = true;

    for(int i=2; i<sqrt((double)MAX_N)+1; i++)
        if(field[i])
            for(int j=i*2; j<MAX_N; j+=i)
                field[j] = false;

    int n = 0;
    while(cin >> n, n){
        int count = 0;
        for(int i=n+1; i<=2*n; i++)
            if(field[i])
                count++;
        cout << count << endl;
    }
    return 0;
}