首页 > 代码库 > POJ 2909 Goldbach's Conjecture(简单题)

POJ 2909 Goldbach's Conjecture(简单题)

【题意简述】:输入一个数,输出有几对素数对可以使他们的和正好等于这个数

【分析】:暴力打表,再暴力循环求解

//268K 125Ms
#include<iostream>
using namespace std;
#define N 35000  // 2^15


bool isprime[N];  
int prime[N],nprime;//prime[N]用来存储素数,nprime是此时一共有多少素数 

void doprime(int n)  
{  
    int i,j;  
    nprime = 1;  
    memset(isprime,true,sizeof(isprime));  
    isprime[1] = 0;  
    prime[0] = 1;  
    for(i = 2;i<=n;i++)  
    {  
        if(isprime[i])  
        {  
            prime[nprime++] = i;  
            for(j = i*i;j<=n;j+=i)  
            {  
                isprime[j] = false;  
            }  
        }  
    }  
}

int main()
{
	int n;
	while(cin>>n,n)
	{
		int ans = 0;
		doprime(n);
		for(int i = 1;i<=nprime;i++)
		{
			for(int j = i;j<=nprime;j++)
			{
				if(n == prime[i]+prime[j])
					ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}


POJ 2909 Goldbach's Conjecture(简单题)