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
反省
和は累積和を持っておいた方が速く求まる