费尔马“二平方”素数问题的提出除２这个特别的素数外，所有的素数都可以分成两类：第一类是被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的表达式，我们起名叫作费尔马“二平方”素数，即如果一个素数能够表示成两个素数的平方和的形式：Ｆ＝Ｘ＊Ｘ＋Ｙ ＊Ｙ （１）其中Ｆ、Ｘ、Ｙ 都是素数，它就是费尔马“二平方”素数。
编程思路本文拟用ｃ 语言编程，求４２亿之内的费尔马“二平方”素数。如果按定义从左向右，先求一个素数Ｆ，然后再去找相应的素数Ｘ、Ｙ ，工作量重复太大。我们可以对上述公式进行分析：１、左侧Ｆ 是素数，它肯定是奇数，那么右侧两式的和也应该是奇数，这样Ｘ 和Ｙ 为一奇一偶，因为奇数的平方还是奇数，偶数的平方还是偶数。Ｘ、Ｙ 又要求是素数，而既是偶数又是素数的数只有一个，就是２。我们假定Ｘ＝２。所以（１）式可以简化为：Ｆ＝２＊２＋Ｙ ＊Ｙ（２）也就是说，费尔马“二平方”素数的表示形式是惟一的。
２、按式（２）由右向左，由小到大找素数Ｙ ，再计算出相应的Ｆ，判断其是否素数。
３、求出素数Ｙ 后将其保存起来，在判断其它数是否素数时可直接用已求出的素数去除，如此反复。
源程序
| #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); } |
| ＃ｉｎｃｌｕｄｅ″ｍａｔｈ ．ｈ″ ｍａｉｎ（） ｛ｕｎｓｉｇｎｅｄ ｌｏｎｇｉ ，ｊ ，ａ［１００００］，ｍ，ｍ１＝３，ｍ２＝７，ｂ ＝１，ｎ ＝０，ｄ ＝１，ｘ＝４０００００００００； ａ［１］＝２； ｌ０：ｆｏｒ （ｉ ＝ｍ１；ｉ ＜＝ｍ２；ｉ ＋＋，ｉ ＋＋） ｛ｉｆ （ｉ ％ａ［１］＝＝０）ｇｏｔｏ ｌ３； ｆｏｒ （ｊ ＝２；ｊ ＜＝ｄ －１；ｊ ＋＋） ｉｆ （ｉ ％ａ［ｊ］＝＝０）ｇｏｔｏ ｌ３； ａ［ｂ ＋＋］＝ｉ ；ｍ＝ｉ ＊ｉ ＋４； ｉｆ （ｍ＞ｘ）ｇｏｔｏ ｌ４； ｆｏｒ （ｊ ＝２；ｊ ＜＝ｂ －２；ｊ ＋＋） ｉｆ （ｍ％ａ［ｊ］＝＝０）ｇｏｔｏ ｌ３； ｐｒｉｎｔｆ（″％２０ｌｕ ＝２＊２＋％５ｌｕ ＊％５ｌｕ″，ｍ，ｉ ，ｉ）； ｉｆ （＋＋ｎ ％２＝＝０）ｐｒｉｎｔｆ（″＼ｎ″）； ｌ３：；｝ｍ１＝ｍ２＋４；ｍ２＝ａ［＋＋ｄ］＊ａ［ｄ］－２； ｇｏｔｏ ｌ０； ｌ４：ｐｒｉｎｔｆ（″＼ｎｔｏｔａｌ ＝％ｌｕ＼ｎ″，ｎ）； ｝ |