AOJ : 1172 - チェビシェフの定理 (Chebyshev's Theorem)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1172&lang=jp
日本語の問題文があるので, 説明省略です

アルゴリズム

エラトステネスの篩で素数表を作成しました.
その素数表を使って, n+1〜2*n の中にいくつ素数があるのか調べました.

プログラム

#define MAX (123456*2)

int main(){
  bool p[MAX+1];
  memset(p,true,sizeof(p));
  p[0] = p[1] = false;
  for(int i=0;i*i<=MAX;i++){
    if(p[i]){
      for(int j=i+i;j<=MAX;j+=i){
        p[j] = false;
      }
    }
  }

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