这道题我们有2种解法，一种解法有时候用GCC交的话会超时，而另一种诗运用了哈希查找的方法，者不得不说我们的崔哲崔老师很厉害。
题目
题目描述
In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:
Every even number greater than 4 can be
written as the sum of two odd prime numbers.
For example:
- 8 = 3 + 5. Both 3 and 5 are odd prime numbers.
- 20 = 3 + 17 = 7 + 13.
- 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.
Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)
Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.
输入
Each test case consists of one even integer n with 6 <= n < 1000000.
Input will be terminated by a value of 0 for n.
输出
示例输入
8 20 42 0
示例输出
8 = 3 + 5 20 = 3 + 17 42 = 5 + 37
下面是第一种解法
（1）这是最开始没有优化的方案（G++交会通过C不可以），在山东理工的ACM上会超时
#include<stdio.h>
#include<math.h>
int decide(int a)
{
int b;
int c=0;
for(b=2;b<=sqrt((double)a);b++) //这里德b++很不省时间，因为如果是偶数的话就一定能被2整除没有必要
{
if(a%b==0)
return 0;
}
return 1;
}
int main()
{
int n;
int i,j;
while(scanf("%d",&n)&&n)
{
for(i=2;i<n;i++)
{
if(decide(i)==1 && decide(n-i)==1)
{
printf("%d = %d + %dn",n,i,n-i);
break;
}
}
}
return 0;
}
//这是优化过的方案，但是并不是最好的
#include<stdio.h>
#include<math.h>
#include<time.h>
int prime(long n)
{
long i,k = 1;
for(i = 3; i <= sqrt(n) ; i = i+2) //由于n是奇数，所以i可以直接由2变为3而且始终让i为奇数，因为n为奇数所以不能整除2的倍数
if(n%i == 0)
{
k = 0;
break;
}
if(k == 1)
return 1;
else
return 0;
}
int main()
{
//clock_t tb,te;
long a,i;
//tb=clock();
while(scanf("%ld", &a),a!=0)
{
for(i = 3 ; i < a;i = i+2) //直接跳过偶数
{
if(prime(i)&&prime(a-i))
{
printf("%ld = %ld + %ldn",a,i,a-i);
break;
}
}
//te=clock();
//printf("%lfn",(tb-te)/CLK_TCK);
}
return 0 ;
}
下面是第二种写法，类似于哈希查找（“崔老师”版）
#include<stdio.h>
#include<math.h>
int p[1000001]={0}; //把所有的都变为零，0代表是素数；（因为这道题限制了数的大小，所以直接设为p[1000001]）
int main()
{
int a,b,c,d;
b=(int)sqrt(1000000); //b是一个最大的因数，取sqrt是为了缩小范围避免重复
p[1]=1; //1既不是素数也不是偶数。直接挂出来排除
for(a=2;a<=b;a++)
{
if(p[a]==0) //当a是素数的时候可以保证a没有因子，减少时间
{d=1;
for(c=2;d<=1000000;c++)
{
d=a*c; //只要是想成能得到的都是非素数
if(d>1000000)break;
p[d]=1;
}
}
}
while(scanf("%d",&a)!=EOF)
{
if(a==0)break;
for(b=2;b<a;b++)
{
if(p[b]==0&&p[a-b]==0)break;
}
printf("%d = %d + %dn",a,b,a-b);
}
return 0;
}
原文链接: https://www.cnblogs.com/0803yijia/archive/2012/02/22/2364025.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/42281
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
