费尔马二平方素数

　2008-03-08 12:41:45　来源：WEB开发网　　　

核心提示：费尔马“二平方”素数问题的提出除２这个非凡的素数外，所有的素数都可以分成两类：第一类是被4除余1的素数，费尔马二平方素数，如5,13,17,2937,41;第二类是被4除余3的素数，如3,7,11,19,23,31，ｍ，ｉ，第一类素数都能表示成两个整数的平方和（第二类则不能），例如：5=1-1+2*213=2*

　　费尔马“二平方”素数　　问题的提出除２这个非凡的素数外，所有的素数都可以分成两类：第一类是被4除余1的素数，如5,13,17,2937,41;第二类是被4除余3的素数，如3,7,11,19,23,31。第一类素数都能表示成两个整数的平方和（第二类则不能）。
　例如：5=1-1+2*213=2*2+3*317=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);
}
结论
运行程序会发现，除“２９＝２＊２＋５＊５”以外，所有的费尔马“二平方”素数个位数字都是３，相应Ｙ的个位数字都是３或７。费尔马“二平方”素数分布（修改程序中变量ｘ的值得到）也很耐人寻味，请看下表（表中１０万以内包含１万以内，下同）：
范围个数最大的一个的表达式
１万１０９４１３＝２＊２＋９７＊９７
１０万２０９７９７３＝２＊２＋３１３＊３１３
１００万４２９９４０１３＝２＊２＋９９７＊９９７
１０００万７６９２２３３７３＝２＊２＋３０３７＊３０３７
１亿１８３９７７５２７７３＝２＊２＋９８８７＊９８８７
１０亿４２７９９９００２４５３＝２＊２＋３１６０７＊３１６０７
２０亿５５１１９８３１８８０９３＝２＊２＋４４５３３＊４４５３３
３０亿６４１２９９３５１２３７３＝２＊２＋５４７１３＊５４７１３
４０亿７１８３９７７４４６４９３＝２＊２＋６３０６７＊６３０６７
费尔马“二平方”素数太少了，４０亿内才７１８个，千万分之二还不到呢。
　随着数的范围的增大，似乎越来越稀少，但再往后永远是这样吗？会不会在某个范围内反而又稠密起来呢？
　费尔马“二平方”素数是无穷多个呢，还是有限多个呢？假如是有限个，又是多少个呢？最大的一个又是什么数呢？
　这些问题的证实可能很简单，也许很复杂，真说不定会成为像“哥德巴赫猜想”那样的谜呢！
----------------------------------------------------------------------
下面是作者原程序,因为是中文全角,上面的就改了一下原文放在下面对照:
＃ｉｎｃｌｕｄｅ″ｍａｔｈ．ｈ″
ｍａｉｎ（）
｛ｕｎｓｉｇｎｅｄｌｏｎｇｉ，ｊ，ａ［１００００］，ｍ，ｍ１＝３，ｍ２＝７，ｂ＝１，ｎ＝０，ｄ＝１，ｘ＝４０００００００００；
ａ［１］＝２；
ｌ０：ｆｏｒ（ｉ＝ｍ１；ｉ＜＝ｍ２；ｉ＋＋，ｉ＋＋）
｛ｉｆ（ｉ％ａ［１］＝＝０）ｇｏｔｏｌ３；
ｆｏｒ（ｊ＝２；ｊ＜＝ｄ－１；ｊ＋＋）
ｉｆ（ｉ％ａ［ｊ］＝＝０）ｇｏｔｏｌ３；
ａ［ｂ＋＋］＝ｉ；ｍ＝ｉ＊ｉ＋４；
ｉｆ（ｍ＞ｘ）ｇｏｔｏｌ４；
ｆｏｒ（ｊ＝２；ｊ＜＝ｂ－２；ｊ＋＋）
ｉｆ（ｍ％ａ［ｊ］＝＝０）ｇｏｔｏｌ３；
ｐｒｉｎｔｆ（″％２０ｌｕ＝２＊２＋％５ｌｕ＊％５ｌｕ″，ｍ，ｉ，ｉ）；
ｉｆ（＋＋ｎ％２＝＝０）ｐｒｉｎｔｆ（″＼ｎ″）；
ｌ３：；｝ｍ１＝ｍ２＋４；ｍ２＝ａ［＋＋ｄ］＊ａ［ｄ］－２；
ｇｏｔｏｌ０；
ｌ４：ｐｒｉｎｔｆ（″＼ｎｔｏｔａｌ＝％ｌｕ＼ｎ″，ｎ）；
｝