AOJ 1172 Chebyshev's Theorem

チェビシェフの定理
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1172&lang=jp

問題概要

n < i <= n*2な素数を数えよ。

解法

エラトステネスの篩

ソース

#include<iostream>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;
const int N = 123456 * 2 + 1;

bool isPrime[N];

void makePrime(){
  rep(i, N)isPrime[i] = true;
  isPrime[1] = isPrime[0] = false;
  rep(i, N){
    if(!isPrime[i])continue;
    for(int j = 2; i * j < N; j++){
      isPrime[j*i] = false;
    }
  }
}

int main(){
  int n;
  makePrime();
  while(cin >> n){
    if(n == 0)break;
    int cnt = 0;
    REP(i, n+1, n*2 + 1){
      if(isPrime[i])cnt++;
    }
    cout << cnt << endl;
  }
  return 0;
}