AOJ 1172 Chebyshev's Theorem

問題

Chebyshev's Theorem | Aizu Online Judge

n<x<=2nの範囲にある素数の数を出力

方針

エラトステネスの篩で素数リストを事前に作っておいて、実際に数える

コード

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
#define rep(i, n) for(int i=0; i<(n); ++i)

const int max_n = 1000000;
int prime[max_n];

int main(void){
    rep(i, max_n) prime[i] = 1;
    prime[0] = 0;
    prime[1] = 0;
    for(int i=2; i<=sqrt(max_n)+1; ++i) {
        if(prime[i] == 1) {
            for(int j=2; i*j<=max_n; ++j) {
                prime[i*j] = 0;
            }
        }
    }
    int n;
    while(cin >> n && n) {
        int ans = 0;
        for(int i=n+1; i<=2*n; ++i) {
            ans += prime[i];
        }
        cout << ans << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1889883

反省

和は累積和を持っておいた方が速く求まる