每天一道英文题,ICPC不自闭(14)

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;
	}
}
上一篇:icpc竞赛退役经验分享


下一篇:每天一道英文题,ICPC不自闭(17)