费尔马“二平方”素数(ZT)

CNOOC

来源:http://www.cppcn.net/cgi-bin/lb5000/topic.cgi?forum=26&topic=187&show=50

问题的提出?除２这个特别的素数外，所有的素数都可以分成两类：第一类是被４除余１的素数，如５，１３，１７，２９，３７，４１；第二类是被４除余３的素数，如３，７，１１，１９，２３，３１。第一类素数都能表示成两个整数的平方和（第二类则不能）。
?例如：?５＝１＊１＋２＊２１３＝２＊２＋３＊３?１７＝１＊１＋４＊４２９＝２＊２＋５＊５?这就是著名的费尔马“二平方”定理。有趣的是：上述等式右侧的数有的又恰恰是两个素数的平方，如１３、２９的表达式，我们起名叫作费尔马“二平方”素数，即如果一个素数能够表示成两个素数的平方和的形式：?Ｆ＝Ｘ＊Ｘ＋Ｙ ＊Ｙ （１）?其中Ｆ、Ｘ、Ｙ 都是素数，它就是费尔马“二平方”素数。
?编程思路?本文拟用ｃ 语言编程，求４２亿之内的费尔马“二平方”素数。?如果按定义从左向右，先求一个素数Ｆ，然后再去找相应的素数Ｘ、Ｙ ，工作量重复太大。我们可以对上述公式进行分析：
?１、左侧Ｆ 是素数，它肯定是奇数，那么右侧两式的和也应该是奇数，这样Ｘ 和Ｙ 为一奇一偶，因为奇数的平方还是奇数，偶数的平方还是偶数。Ｘ、Ｙ 又要求是素数，而既是偶数又是素数的数只有一个，就是２。我们假定Ｘ＝２。所以（１）式可以简化为：?Ｆ＝２＊２＋Ｙ ＊Ｙ（２）?也就是说，费尔马“二平方”素数的表示形式是惟一的。
?２、按式（２）由右向左，由小到大找素数Ｙ ，再计算出相应的Ｆ，判断其是否素数。
?３、求出素数Ｙ 后将其保存起来，在判断其它数是否素数时可直接用已求出的素数去除，如此反复。
?源程序?
＃ｉｎｃｌｕｄｅ″ｍａｔｈ ．ｈ″?
ｍａｉｎ（）?
｛ｕｎｓｉｇｎｅｄ ｌｏｎｇｉ ，ｊ ，ａ［１００００］，ｍ，ｍ１＝３，ｍ２＝７，?ｂ ＝１，ｎ ＝０，ｄ ＝１，ｘ＝４０００００００００；?
ａ［１］＝２；?
ｌ０：ｆｏｒ （ｉ ＝ｍ１；ｉ ＜＝ｍ２；ｉ ＋＋，ｉ ＋＋）?
｛ｉｆ （ｉ ％ａ［１］＝＝０）ｇｏｔｏ ｌ３；?
ｆｏｒ （ｊ ＝２；ｊ ＜＝ｄ －１；ｊ ＋＋）?
ｉｆ （ｉ ％ａ［ｊ］＝＝０）ｇｏｔｏ ｌ３；?
ａ［ｂ ＋＋］＝ｉ ；ｍ＝ｉ ＊ｉ ＋４；?
ｉｆ （ｍ＞ｘ）ｇｏｔｏ ｌ４；?
ｆｏｒ （ｊ ＝２；ｊ ＜＝ｂ －２；ｊ ＋＋）?
ｉｆ （ｍ％ａ［ｊ］＝＝０）ｇｏｔｏ ｌ３；?
ｐｒｉｎｔｆ（″％２０ｌｕ ＝２＊２＋％５ｌｕ ＊％５ｌｕ″，ｍ，ｉ ，ｉ）；?
ｉｆ （＋＋ｎ ％２＝＝０）ｐｒｉｎｔｆ（″＼ｎ″）；?
ｌ３：；｝?ｍ１＝ｍ２＋４；ｍ２＝ａ［＋＋ｄ］＊ａ［ｄ］－２；?
ｇｏｔｏ ｌ０；?
ｌ４：ｐｒｉｎｔｆ（″＼ｎｔｏｔａｌ ＝％ｌｕ＼ｎ″，ｎ）；?
｝
?结论?
运行程序会发现，除“２９＝２＊２＋５＊５”以外，所有的费尔马“二平方”素数个位数字都是３，相应Ｙ 的个位数字都是３或７。?费尔马“二平方”素数分布（修改程序中变量ｘ 的值得到）也很耐人寻味，请看下表（表中１０万以内包含１万以内，下同）：
?范围个数最大的一个的表达式?
１万１０９４１３＝２＊２＋９７＊９７?
１０万２０９７９７３＝２＊２＋３１３＊３１３?
１００万４２９９４０１３＝２＊２＋９９７＊９９７?
１０００万７６９２２３３７３＝２＊２＋３０３７＊３０３７?
１亿１８３９７７５２７７３＝２＊２＋９８８７＊９８８７?
１０亿４２７９９９００２４５３＝２＊２＋３１６０７＊３１６０７?
２０亿５５１１９８３１８８０９３＝２＊２＋４４５３３＊４４５３３?
３０亿６４１２９９３５１２３７３＝２＊２＋５４７１３＊５４７１３?
４０亿７１８３９７７４４６４９３＝２＊２＋６３０６７＊６３０６７?
费尔马“二平方”素数太少了，４０亿内才７１８个，千万分之二还不到呢。
?随着数的范围的增大，似乎越来越稀少，但再往后永远是这样吗？会不会在某个范围内反而又稠密起来呢？
?费尔马“二平方”素数是无穷多个呢，还是有限多个呢？如果是有限个，又是多少个呢？最大的一个又是什么数呢？
?这些问题的证明可能很简单，也许很复杂，真说不定会成为像“哥德巴赫猜想”那样的谜呢！

CNOOC

这家伙的排版还真够难看的。

goldedge

    
说点简单的啊
呵呵

这家伙的排版还真够难看的。