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; }