费尔马二平方素数
2008-03-08 12:41:45 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閻愵剙鍔ょ紓宥咃躬瀵鎮㈤崗灏栨嫽闁诲酣娼ф竟濠偽i鍓х<闁绘劦鍓欓崝銈囩磽瀹ュ拑韬€殿喖顭烽幃銏ゅ礂鐏忔牗瀚介梺璇查叄濞佳勭珶婵犲伣锝夘敊閸撗咃紲闂佽鍨庨崘锝嗗瘱闂備胶顢婂▍鏇㈠箲閸ヮ剙鐏抽柡鍐ㄧ墕缁€鍐┿亜韫囧海顦﹀ù婊堢畺閺屻劌鈹戦崱娆忓毈缂備降鍔庣划顖炲Φ閸曨垰绠抽悗锝庝簽娴犻箖姊洪棃娑欐悙閻庢矮鍗抽悰顕€宕堕澶嬫櫖濠殿噯绲剧€笛囧箲閸ヮ剙钃熼柣鏂挎憸閻熷綊鏌涢…鎴濇灈妞ゎ剙鐗嗛—鍐Χ鎼粹€茬凹缂備緡鍠楅幐鎼佹偩閻戣棄纭€闁绘劕绉靛Λ鍐春閳ь剚銇勯幒鎴濐伀鐎规挷绀侀埞鎴︽偐閹绘帩浼€缂佹儳褰炵划娆撳蓟濞戞矮娌柟瑙勫姇椤ユ繈姊洪柅鐐茶嫰婢т即鏌熼搹顐e磳闁挎繄鍋涢埞鎴犫偓锝庘偓顓涙櫊閺屽秵娼幏灞藉帯闂佹眹鍊曢幊鎰閹惧瓨濯撮柛鎾村絻閸撳崬顪冮妶鍡楃仸闁荤啿鏅涢悾鐑藉Ψ瑜夐崑鎾绘晲鎼粹剝鐏嶉梺缁樻尰濞叉﹢濡甸崟顖氱疀闂傚牊绋愮花鑲╃磽娴h棄鐓愭慨妯稿妿濡叉劙骞樼拠鑼槰闂佸啿鎼崐濠毸囬弶搴撴斀妞ゆ梻銆嬪銉︺亜椤撶偛妲婚柣锝囧厴楠炴帡骞嬮弮鈧悗濠氭⒑鐟欏嫭鍎楅柛妯衡偓鐔插徍濠电姷鏁告慨鐑藉极閸涘﹥鍙忔い鎾卞灩绾惧鏌熼崜褏甯涢柍閿嬪灦閵囧嫰骞掗崱妞惧缂傚倷绀侀ˇ閬嶅极婵犳氨宓侀柛鈩冪⊕閸婄兘鏌涘┑鍡楊伀妞ゆ梹鍔曢埞鎴︽倻閸モ晝校闂佸憡鎸婚悷锔界┍婵犲洦鍤冮柍鍝勫暟閿涙粓姊鸿ぐ鎺戜喊闁告瑥楠搁埢鎾斥堪閸喓鍘搁柣蹇曞仧绾爼宕戦幘璇茬疀濞达絽鎲¢崐顖炴⒑绾懎浜归悶娑栧劦閸┾偓妞ゆ帒鍟惃娲煛娴e湱澧柍瑙勫灴閹瑩寮堕幋鐘辨闂備礁婀辨灙闁硅姤绮庨崚鎺楀籍閸喎浠虹紓浣割儓椤曟娊鏁冮崒娑氬幈闂佸搫娲㈤崝宀勬倶閻樼粯鐓曢柟鑸妼娴滄儳鈹戦敍鍕杭闁稿﹥鐗犲畷婵嬫晝閳ь剟鈥﹂崸妤€鐒垫い鎺嶈兌缁犲墽鈧厜鍋撳┑鐘辩窔閸嬫鈹戦纭烽練婵炲拑绲垮Σ鎰板箳閹冲磭鍠撻幏鐘绘嚑閼稿灚姣愰梻鍌氬€烽懗鑸电仚濠电偛顕崗妯侯嚕椤愩倖瀚氱€瑰壊鍠栧▓銊︾節閻㈤潧校缁炬澘绉瑰鏌ュ箵閹烘繄鍞甸柣鐘烘鐏忋劌顔忛妷褉鍋撶憴鍕碍婵☆偅绻傞~蹇涙惞閸︻厾锛滃┑鈽嗗灠閹碱偊锝炲鍥╃=濞达綁顥撻崝宥夋煙缁嬪灝鏆遍柣锝囧厴楠炲鏁冮埀顒傜不婵犳碍鍋i柛銉戝啰楠囬悗瑙勬尭缁夋挳鈥旈崘顔嘉ч柛鈩兠棄宥囩磽娴e壊鍎愰柛銊ュ缁顓兼径瀣偓閿嬨亜閹哄秶顦︾€殿喖鐏濋埞鎴﹀煡閸℃浠梺鍛婎焼閸曨収娲告俊銈忕到閸燁垶宕愰崹顐e弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚�

核心提示:费尔马“二平方”素数问题的提出除2这个非凡的素数外,所有的素数都可以分成两类:第一类是被4除余1的素数,费尔马二平方素数,如5,13,17,2937,41;第二类是被4除余3的素数,如3,7,11,19,23,31,m,i ,第一类素数都能表示成两个整数的平方和(第二类则不能),例如:5=1-1+2*213=2*
费尔马“二平方”素数 问题的提出除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);
}
结论
运行程序会发现,除“29=2*2+5*5”以外,所有的费尔马“二平方”素数个位数字都是3,相应Y 的个位数字都是3或7。费尔马“二平方”素数分布(修改程序中变量x 的值得到)也很耐人寻味,请看下表(表中10万以内包含1万以内,下同):
范围个数最大的一个的表达式
1万109413=2*2+97*97
10万2097973=2*2+313*313
100万42994013=2*2+997*997
1000万769223373=2*2+3037*3037
1亿18397752773=2*2+9887*9887
10亿427999002453=2*2+31607*31607
20亿5511983188093=2*2+44533*44533
30亿6412993512373=2*2+54713*54713
40亿7183977446493=2*2+63067*63067
费尔马“二平方”素数太少了,40亿内才718个,千万分之二还不到呢。
随着数的范围的增大,似乎越来越稀少,但再往后永远是这样吗?会不会在某个范围内反而又稠密起来呢?
费尔马“二平方”素数是无穷多个呢,还是有限多个呢?假如是有限个,又是多少个呢?最大的一个又是什么数呢?
这些问题的证实可能很简单,也许很复杂,真说不定会成为像“哥德巴赫猜想”那样的谜呢!
----------------------------------------------------------------------
下面是作者原程序,因为是中文全角,上面的就改了一下原文放在下面对照:
#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);
}
更多精彩
赞助商链接