POJ 2262 Goldbach's Conjecture
题目翻译
1742年,德国业余数学家克里斯蒂安·戈德巴赫(Christian Goldbach)致函莱昂哈德·欧拉(Leonhard Euler),他在信中做出以下推测:
每一个大于4的偶数都可以写为两个奇数素数之和。
举个栗子:
8 = 3 + 5. 3和5都是奇数素数。
20 = 3 + 17 = 7 + 13。
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23。
今天,这个猜想是否正确还没有得到证实。(哦,等等,我当然有证据,但写在这一页的页边太长了。)无论如何,你现在的任务是验证哥德巴赫对所有小于一百万的偶数的猜想。
输入
输入将包含一个或多个测试用例。每个测试用例由一个偶数整数 n 组成,其中 6<=n<1000000。对于 n,输入将以 0 值终止。
输出
对于每个测试用例,打印一行形式为 n=a+b,其中 a 和 b 是奇数素数。数字和运算符应该用一个空格隔开,就像下面的示例输出一样。如果有多对奇数素数加起来等于 n,则选择差值 b-a 最大的一对。如果没有这样的一对,就写一行“哥德巴赫的猜想是错误的。”(很明显这句话没用)
样例
输入
8 20 42 0
输出
8 = 3 + 5 20 = 3 + 17 42 = 5 + 37
解题思路
其实这道题有很大一个bug,n 是偶数整数,而偶数素数只有 2 不论和其他哪个素数合起来必然为奇数,所以这道题没必要考虑那么多,直接筛出来素数,然后从小到大找就可以了。
代码示例
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a;
int l,r;
int cnt;
int prime[1001000];
bool isprime[1001000];
void prepare(int x){
memset(isprime,1,sizeof(isprime));
for(int i=2;i<=x;i++){
if(isprime[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&prime[j]*i<=x;j++){
isprime[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
}
int main(){
prepare(1000000);
while(cin>>a){
if(a==0) break;
for(int i=1;i<=cnt;i++){
if(isprime[a-prime[i]]){
l=prime[i];
r=a-prime[i];
break;
}
}
cout<<a<<" = "<<l<<" + "<<r<<endl;
}
}