600      技术社区[云栖]

POJ 1595 素数筛法

题意让求一段素数中间的几个素数 用素数筛法筛出范围内的素数然后确定一下就行了 注意题目中1也算作素数了 具体看代码

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define max 2000
bool isprime[max];
int prime[max],nprime;
void getprime()
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    long long i,j;
    nprime=1;
    prime[1]=1;
    for(i=2; i<max; i++)
    {
        if(isprime[i])
            prime[++nprime]=i;
        for(j=i*i; j<max; j+=i)
            isprime[j]=0;
    }
}
int main()
{
    getprime();
    int n,c,f=0;
    while(cin>>n>>c)
    {
        int s;
        if(f)
            cout<<endl;
        f=1;
        for(s=1; prime[s]<=n; s++);
        s--;
        cout<<n<<" "<<c<<": ";
        if(2*c>=s)
            for(int i=1; i<=s; i++)
                if(i!=s)
                    cout<<prime[i]<<" ";
                else
                    cout<<prime[i]<<endl;
        else if(s%2)
            for(int i=s/2+1,j=-c+1; j<=c-1; j++)
                if(j!=c-1)
                    cout<<prime[i+j]<<" ";
                else
                    cout<<prime[i+j]<<endl;
        else if(s%2==0)
            for(int i=s/2,j=-c+1; j<=c; j++)
                if(j!=c)
                    cout<<prime[i+j]<<" ";
                else
                    cout<<prime[i+j]<<endl;
    }
    return 0;
}

最后更新：2017-04-04 07:03:39

  上一篇： Apache Tika:通用的内容分析工具

  下一篇： Core Data浅谈系列之三 ： 了解NSManagedObject和NSPredicate