p3511.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1000100;
vector < int > p;
bool isnp[MAXN+1] = {};
int main(){
    for(int i = 2;i * i <= MAXN;++i)
        if(!isnp[i])
            for(int j = i*i;j <= MAXN;j += i)
                isnp[j] = true;
    for(int i = 2;i < MAXN;++i)
        if(!isnp[i]) p.push_back( i );
    int U,L,u,l;
    scanf("%d%d",&l,&u);
    while(u != -1 || l != -1){
        U = u; L = l;
        if(U < 0) U = 0;
        if(L < 0) L = 0;
        int ans1(0),ans2(0);
        vector<int>::iterator i,j;
        i = lower_bound(p.begin(),p.end(),L);
        j = upper_bound(p.begin(),p.end(),U);
        ans1 = j - i;
        for(;*i <= U;++i)
            if((*i) % 4 == 1) ans2++;
        if(L <= 2 && U >= 2) ans2++;
        printf("%d %d %d %d\n",l,u,ans1,ans2);
        scanf("%d%d",&l,&u);
    }
}