poj1595 prime cuts（快速筛选）

本文主要是介绍poj1595 prime cuts（快速筛选），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：  给定一个数字N，将1到N中的所有质数按照中心值为c的规定输出，规则详见题目。

本题不难，但是要注意这里1也算是素数列中的一员。其它的都是小事儿啦，用快速筛选找到1--1000内所有的素数和合数。然后A了。

#include <iostream>
#include<cstdio>
using namespace std;
bool notpri[1001];
int prime[1001],cnt=0;
void getprime(){  //快速筛选。int i,j;prime[++cnt]=1;for(i=2;i<=1000;i++){if(!notpri[i])prime[++cnt]=i;for(j=2;j<=cnt&&prime[j]*i<=1000;j++){notpri[prime[j]*i]=1;if(i%prime[j]==0)break;}}
}
int prisum[1001];  //记录前N个数字里有多少个素数。
void stat(){int t=2;prisum[1]=1;prisum[2]=2; // 1 is a primerfor(int i=3;i<=1000;i++){if(!notpri[i])t++;prisum[i]=t;}
}
int main()
{getprime();stat();int N,C;while(~scanf("%d%d",&N,&C)){int sum,i;//cout<<prisum[N]<<endl;if(prisum[N]%2)sum=2*C-1;else sum=2*C;printf("%d %d: ",N,C);if(sum>=prisum[N])for(i=1;i<=prisum[N];i++){printf("%d ",prime[i]);}else {int start=(prisum[N]-sum)/2+1;  //设置print的起点for(i=start;i<start+sum;i++){printf("%d ",prime[i]);}}printf("\n\n");}return 0;
}

这篇关于poj1595 prime cuts（快速筛选）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---