1262 寻找素数对.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1262 寻找素数对
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
#include <iostream>
using namespace std;

const int mMax=10000;

/************筛选法求素数***************/
int sievePrime(int savenum[],int n)
{
    int ca,temp,now;
    int num[mMax]={0};
    for(ca=2;ca<=n;ca++)
    {
        if(num[ca]==0)
        {
            temp=ca+ca;
            while(temp<=n)
            {   num[temp]=1;temp+=ca;}
        }
    }

    for(ca=2,now=0;ca<=n;ca++)
        if(num[ca]==0)
        {   savenum[now]=ca;now++;}

    return now-1;
}

int fibFind(int num[],int findnum)
{
    int f1,f2,temp,now;
    bool flag;
    f1=1;f2=1;now=0;flag=true;
    while(flag)
    {
        flag=false;
        while(num[now+f2-1]<=findnum)
        {
            if(num[now+f2-1]==findnum)
            {   return now+f2-1;}
            else
            {
                temp=f2;
                f2=f1+f2;
                f1=temp;
                flag=true;
            }
        }
        now+=f1;
        f1=1;f2=1;
    }
    return now-2;
}

int main()
{
    int m,a,b,size,now,left,cb,ca;
    int prime[1230];
    size=sievePrime(prime,mMax);
    while(cin>>m)
    {
        now=fibFind(prime,m/2);
        for(ca=now;ca>=0;ca--)
        {
            left=m-prime[ca];
            cb=now;
            while(left>prime[cb])
            {   cb++;}
            if(left==prime[cb])
            {   a=prime[ca];b=left;break;}
        }
        cout<<a<<" "<<b<<endl;
    }
    return 0;
}