四个素数之和问题.docx

问题描述:欧拉证明素数有无穷多个。但每个整数能表示成4个素数之和吗？输入：每行输入一个整数N(N=10 000 000)，它是你需要把它表示成4个素数之和的数。输出：对于每个输入行都有一个输出行，每行包含符合要求的4个素数。如果该素数不能表示为4个素数之和，那么输出一行不能。也可能有很多组解，任何合理的解都将被接受。输入样例： 输出样例:24 3 11 3 7363 7 13 134611 11 17 7代码：#include#include#includeusing namespace std;const int MAXLEN=10001;long modular_power1(long a,long r,long m)/求模幂ar mod m的值long d,t;d=1;t=a;while(r0)if(r%2)=1)d=(d*t)%m;r/=2;t=t*t%m;return d;/素数测试算法代码(Miller-Rabin素数测试算法)bool Miller_Rabin(long long a,long long n)long long d,t,bitnum,bit;bit=11;d=1;while(bit0)t=d;d=(d*d)%n;if(d=1)&(t!=1)&(t!=n-1)return true;if(bit&bitnum)!=0)d=(d*a)%n;bit=bit1;if(d!=1)return true;return false;void G_maini(int n,int *a,int *b)/用到上面的素数测试算法，此函数用来验证哥德巴赫猜想(每个大/于4的偶数都可以写成两个奇素数之和)int a1,a2,b1,b2,k;if(n3)|(n%2=1)coutErrorendl;elseif(n=4|n=6)*a=n/2;*b=n/2;elseif(n=8)*a=3;*b=5;else if(n=10)*a=3;*b=7;elsesrand(time(NULL);for(k=3;k=n-k-1)a1=(int(rand()%(n-k)+1);/随机选取a1if(Miller_Rabin(a1,n-k)continue;/第次Miller_Rabin素数测试elseb1=1;while(b1=1)|(b1=n-k-1)|b1=a1)b1=(int(rand()%(n-k)+1);/随机选取b1if(Miller_Rabin(b1,n-k)continue;/第次Miller_Rabin素数测试else*a=k;*b=n-k;break;elsea1=1;a2=1;while(a1=1)|(a1=k-1)a1=(int(rand()%k)+1);/随机选取a1while(a2=1)|(a2=n-k-1)a2=(int(rand()%(n-k)+1);/随机选取a2if(Miller_Rabin(a1,k)|Miller_Rabin(a2,n-k)continue;/第次Miller_Rabin素数测试elseb1=1;b2=1;while(b1=1)|(b1=k-1)|b1=a1)b1=(int(rand()%k)+1);/随机选取b1while(b2=1)|(b2=k-1)|b2=a1)b2=(int(rand()%(n-k)+1);/随机选取b2if(Miller_Rabin(b1,k)|Miller_Rabin(b2,n-k)continue;/第次Miller_Rabin素数测试else*a=k;*b=n-k;break;/return 0;bool prime(int n)/判断n是否是素数，若是则返回true int j; if(n=2)return true; if(n=1|n%2=0)return false; j=3; while(j=int(sqrt(long double(n) if(n%j=0)return false; j+=2; return true;void OddNumber(int num,int *a,int *b,int *a1,int *a2,int *b1,int *b2)/num为奇数时,这里的num/是待分解的数if(*a%2!=0)/当a是奇数时,则b为偶数，依据哥德巴赫猜想，b(大于)可以分解为两个素数之和；/如果a不能分解为两个素数之和，则num不能分解为四个素数之和if(prime(*a-2)/a-2是素数*a1=2,*a2=*a-2;/求b1和b2用哥德巴赫猜想G_maini(*b,b1,b2);else cout不能分解为四个素数;else/b是奇数，处理同上if(prime(*b-2)/b-2是素数*b1=2,*b2=*b-2;/求a1和a2用哥德巴赫猜想G_maini(*a,a1,a2);elsecoutnum;int a,b;int a1,a2,b1,b2;/分别存储分解后的数a=num/2;b=num-a;if(num%2=0)/num为偶数的情况/num为偶数的情况下分两种情况：、a=b为偶数，、a=b为奇数if(a%2=0)/1/依据哥德巴赫猜想G_maini(a,&a1,&a2);b1=a1,b2=a2;else/2 为奇数的情况考虑不全，当num=46时，应有解，程序得到的结果是错误的a=a-1;b=b+1;G_maini(a,&a1,&a2);G_maini(b,&b1,&b2);else/num为奇数的情况,这里说明一下，当num为奇数时，则可将num分解为一个奇数和一个偶数。/据哥德巴赫猜想可知，偶数可以分解为两个素数之和。由于偶素数只