ACM 543 Goldbach’s Conjecture
找一個質數a,再將n-a 去做判斷看使否為質數!!
速度:程式碼(1)>(2)>(3)
(1)為線性篩法(快5Xms)(乾淨俐落)
(2)表建表(中1XXms)(有點複雜)
(3)普通建表(慢6XXms)(還算可以)
/********************************************************/
#include<stdio.h>
#include<stdlib.h>
char line[1000001]={0};
main()
{
int a,b,top=0;
for(a=3;a<1000001/2;a=a+2)
if(line[a]==0)
{
for(b=3;a*b<=1000000;b=b+2)
line[a*b]=1;
}
int n;
while(scanf("%d",&n)==1&&n!=0)
{
for(a=3;a<=n/2;a=a+2)
if(line[a]==0&&line[n-a]==0)
{printf("%d = %d + %d\n",n,a,n-a);break;}
}
return 0;
}
/********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
int a,b,c,n;
int math[500]={0},m=1;
math[0]=3;
for(a=5;a<1000;a=a+2)
{
int flag=0;
for(b=0;math[b]<=sqrt(a);b++)
{
if(a%math[b]==0)
{
flag=1;
break;
}
}
if(flag==0)
{
math[m]=a;
m++;
}
}
while(scanf("%d",&n)==1&&n!=0)
{
int flag=0;
for(a=0;a<m;a++)
{
int nn=n-math[a],flag1=0;
for(b=0;math[b]<=(int)sqrt(nn)&&b<m;b++)
{
if(nn%math[b]==0)
{
flag1=1;break;
}
}
if(flag1==0)
{
flag=1;
printf("%d = %d + %d\n",n,math[a],nn);
break;
}
}
if(flag==0)
printf("Goldbach's conjecture is wrong.\n");
}
return 0;
}
/********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
int a,b,c,n;
int math[300]={0},m=0;
for(a=3;a<300;a++)
{
int flag=0;
for(b=2;b<=(int)sqrt(a);b++)
{
if(a%b==0)
{
flag=1;
break;
}
}
if(flag==0)
{
math[m]=a;
m++;
}
}
while(scanf("%d",&n)==1&&n!=0)
{
int flag=0;
for(a=0;a<m;a++)
{
int nn=n-math[a],flag1=0;
for(b=2;b<=(int)sqrt(nn);b++)
{
if(nn%b==0)
{
flag1=1;break;
}
}
if(flag1==0)
{
flag=1;
printf("%d = %d + %d\n",n,math[a],nn);
break;
}
}
if(flag==0)
printf("Goldbach's conjecture is wrong.\n");
}
return 0;
}