PKU 1595 Prime Cuts

http://poj.org/problem?id=1595
1〜Nまでの数のうち、素数であるものを順番に並べて、真ん中から小さい方にC個、大きい方へC個出力するというような問題。

やや易。

1も素数に含めるらしいです。あと、最後の改行を忘れてました。

bool pr[2001];
int npr[500];

main(){
  fill(pr,pr+2001,true);

  pr[0]=false;
  for(int i=2;i<2001;i++){
    if(pr[i]==false)continue;
    for(int j=2*i;j<2001;j+=i)pr[j]=false;
  }
  int pos=0;
  rep(i,2001)if(pr[i])npr[pos++]=i;

  int n,c;
  while(cin>>n>>c){
    int la=0;
    while(npr[la]<=n)++la;
    cout<<n<<' '<<c<<':';
    for(int i=max(0,(la+1)/2-c);i<min(la,la/2+c);i++)cout<<' '<<npr[i];
    cout<<endl<<endl;
  }
}