ICPC 国内予選2011A チェビシェフの定理 AOJ 1172
解法:エラトステネス、累積和
やるだけ。難易度-5
#include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> P; typedef tuple<int, int, int> T; const ll MOD=1e9+7; const ll INF=1e18; int dx[]={1, -1, 0, 0}; int dy[]={0, 0, 1, -1}; int sum[250005]; bool prime[250005]; int main(){ prime[1] = true; int a = 0; for(int i = 2;i < 250000;i++){ if(prime[i] == false){ a++; for(int j = 1;i*j < 250000;j++){ prime[i*j] = true; } } sum[i] = a; } while(true){ int n; cin >> n; if(n == 0) break; cout << sum[n*2] - sum[n] << endl; } }