费尔马“二平方”素数问题的提出除2这个特别的素数外,所有的素数都可以分成两类:第一类是被4除余1的素数,如5,13,17,2937,41;第二类是被4除余3的素数,如3,7,11,19,23,31.第一类素数都能表示成两个整数的平方和(第二类则不能)。
例如:5=1-1+2*213=2*2+3*317=1*1+4*4 29=2*2+5*5这就是著名的费尔马“二平方”定理。有趣的是:上述等式右侧的数有的又恰恰是两个素数的平方,如13,29的表达式,我们起名叫作费尔马“二平方”素数,即如果一个素数能够表示成两个素数的平方和的形式:F=X*X+Y *Y (1)其中F、X、Y 都是素数,它就是费尔马“二平方”素数。
编程思路本文拟用c 语言编程,求42亿之内的费尔马“二平方”素数。如果按定义从左向右,先求一个素数F,然后再去找相应的素数X、Y ,工作量重复太大。我们可以对上述公式进行分析:1、左侧F 是素数,它肯定是奇数,那么右侧两式的和也应该是奇数,这样X 和Y 为一奇一偶,因为奇数的平方还是奇数,偶数的平方还是偶数。X、Y 又要求是素数,而既是偶数又是素数的数只有一个,就是2。我们假定X=2。所以(1)式可以简化为:F=2*2+Y *Y(2)也就是说,费尔马“二平方”素数的表示形式是惟一的。
2、按式(2)由右向左,由小到大找素数Y ,再计算出相应的F,判断其是否素数。
3、求出素数Y 后将其保存起来,在判断其它数是否素数时可直接用已求出的素数去除,如此反复。
源程序
#include<math.h> void main() { unsigned long i,j,a[10000],m,m1=3,m2=7,b=1,n=0,d=1,x=4000000000; a[1]=2; 10:for(i=m1;i<=m2;i++,i++) { if(i%a[1]==0) goto 13; for(j=2;j<=d-1;j++) if(i%a[j]==0) goto 13; a[b++]=i; m=i*i+4; if(m>x) goto 14; for(j=2;j<=b-2;j++) if(m%a[j]==0) goto 13; printf("%20lu=2*2+%5lu*%5lu",m,i,i); if(++n%2==0) printf("\n"); 13:m1=m2+4; m2=a[++d]*a[d]-2; goto 10; 14:printf("\ntotal=%lu\n",n); } |
#include″math .h″ main() {unsigned longi ,j ,a[10000],m,m1=3,m2=7,b =1,n =0,d =1,x=4000000000; a[1]=2; l0:for (i =m1;i <=m2;i ++,i ++) {if (i %a[1]==0)goto l3; for (j =2;j <=d -1;j ++) if (i %a[j]==0)goto l3; a[b ++]=i ;m=i *i +4; if (m>x)goto l4; for (j =2;j <=b -2;j ++) if (m%a[j]==0)goto l3; printf(″%20lu =2*2+%5lu *%5lu″,m,i ,i); if (++n %2==0)printf(″\n″); l3:;}m1=m2+4;m2=a[++d]*a[d]-2; goto l0; l4:printf(″\ntotal =%lu\n″,n); } |