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