poj1595 0ms water

#include<cstdio>
using namespace std;
//water 
//素数打表基操吧， 然后预处理维护一个前缀和就好了
const int N = 1000;
bool Prim[N+5]= {0};
int sum[N+5]= {0};
void Print_Prime()
{
    Prim[1] = 0;
    Prim[0] = 1;
    for(int i = 2; i<=N; ++i)
        if(!Prim[i])
            for(int j = i*2; j<=N; j+=i)
                Prim[j] = true;
}
void Pretreatment()
{
    Print_Prime();
    for(int i = 1; i<=N; ++i)
    {
        sum[i] = sum[i-1];
        if(!Prim[i])
            sum[i]++;
    }
}
int main()
{
    int n,c;
    Pretreatment();
    while(~scanf("%d%d",&n,&c))
    {
        printf("%d %d:",n,c);
        c = (sum[n]&1) ? (2*c-1) : (2*c);
        int i,cnt;
        for(i = 0,cnt = 0; i<=n; ++i)
        {
            if(!Prim[i])
                cnt++;
            if(sum[n]<=c||2*cnt==sum[n]-c)
                break;
        }
        for(i=i+1; i<=n&&c; ++i)
            if(!Prim[i])
            {
                c--;
                printf(" %d",i);
            }
        printf("\n\n");
    }
    return 0;
}