2012湖南邀请赛A题
/*方法：打表 解析：奇数 = 奇合数 + 偶数假设某个奇数 x ，那么只有 x - 4 之前的奇合数才符合要求 */#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define manx 1000009long long x[manx];bool s[manx];void prime(){ for(int i=0;i<manx;i++) x[manx]=0,s[i]=0; for(int i=2;i*i<manx;i++){ if(!s[i]){ for(int j=2;j*i<manx;j++) s[j*i]=1; } } }void fan(){ int len=0; for(int i=9;i<manx;i++){ if(s[i] && i%2) len++; x[i]=len; }}int main(){ int n; prime(); fan(); while(cin>>n){ cout<<x[n]<<endl; }}