付媛媛　錢俊彤　錢冠州　馬銘里

【摘要】隨著自然數(shù)的不斷增大，素數(shù)的個數(shù)也在不斷增多，而素數(shù)的不斷增加導致因數(shù)數(shù)目的不斷擴大，這是否意味著自然數(shù)、因數(shù)增加到一定程度后所有的自然數(shù)都能夠被1和自身以外的因數(shù)分解而沒有新的素數(shù)了呢？借助計算機對自然數(shù)中所蘊涵的素數(shù)進行計算、統(tǒng)計分析，其規(guī)律顯示素數(shù)個數(shù)將隨著自然數(shù)的增大而增加下去，素數(shù)是沒有尾的.此次借助計算機算出的最大一個素數(shù)是2099999999.

【關鍵詞】素數(shù)；自然數(shù)；因數(shù)

素數(shù)即只能被1和它自身整除的自然數(shù).隨著自然數(shù)的不斷增大，素數(shù)的個數(shù)也在不斷增多，就意味著因數(shù)的不斷增加.自然數(shù)的不斷增大和因數(shù)的增多就意味著素數(shù)的個數(shù)就可能要減少，那么當自然數(shù)大到某個數(shù)后，是否就沒有素數(shù)了，就是說素數(shù)是否有尾呢？借助計算機對素數(shù)個數(shù)進行計算、統(tǒng)計、分析，顯示出二者的變化關系趨勢.

1.素數(shù)的算法

算法1：根據(jù)素數(shù)的定義，判定某個自然數(shù)n是否為素數(shù)，只需用2到n-1去除n，如果都除不盡則n是素數(shù)，否則只要其中有一個數(shù)能整除則n不是素數(shù).這種根據(jù)定義計算素數(shù)需要執(zhí)行n-2次除法，計算量大，當分析計算較大自然數(shù)的素數(shù)時耗時長.

優(yōu)化算法2：很顯然，當因數(shù)大于自然數(shù)n的一半，即n/2時，只剩1個因數(shù)n可以整除n，故在判定自然數(shù)n是否為素數(shù)只需計算2～n/2范圍內有無因數(shù)即可，計算工作量較算法1減少一半.

優(yōu)化算法3：若n能分解成因數(shù)i×j（i，j是大于2，小于n的整數(shù)），則i、j取值范圍為：大于等于2而小于等于n/2，因數(shù)i、j所組成的數(shù)列中按大小順序排列二者具有關系i×j=n，如圖1所示.數(shù)列的中心位置為n，故從2計算到n是否有因數(shù)存在即可判斷出n是否為素數(shù)，而從n到n/2實際上是重復計算.這種算法較算法2計算量減少n/2，當n較大，例如為1億時，計算量僅為算法2的1/5000，計算量大幅減少.

優(yōu)化算法4：在計算機編程計算時可進一步優(yōu)化計算工作量.首先，自然數(shù)n的末位數(shù)為偶數(shù)或5時則該數(shù)可以被2或5整除，故該自然數(shù)一定不是素數(shù).在編程時可以只對末位數(shù)為除5以外的奇數(shù)進行素數(shù)判斷，進一步減少需要進行素數(shù)判斷的自然數(shù).其次，在算法3中因數(shù)i取值范圍2～n，末位數(shù)為偶數(shù)或5的因數(shù)進行i×j=n的運算結果必然是末位數(shù)為偶數(shù)或5的自然數(shù)n，故對于需要進行判斷的末位數(shù)為除5以外的奇數(shù)自然數(shù)n而言末位數(shù)為偶數(shù)或5的因數(shù)i一定不是自然數(shù)n的因數(shù).在自然數(shù)n與因數(shù)i的整除運算判斷素數(shù)是因數(shù)i的實際運算范圍可以確定為3～n中末位數(shù)為除5以外的奇數(shù)，這樣可以進一步減少計算機運算工作量.

通過上述分析對比可見經(jīng)過3步優(yōu)化后計算量大幅度減少，且當計算的自然數(shù)n越大時，其算法的優(yōu)越性更加明顯.例如在計算出1億～2億之間的自然數(shù)n的所有素數(shù)時，算法1的整除運算量為1016次，而算法4的整除運算量為1.6×1011次，提高效率6.2×104倍.

2.計算結果分析

由于個人PC機性能及時間因素限制，只分析計算到自然數(shù)21億以內的素數(shù).經(jīng)過約半年時間運算得到的21億以內最大的素數(shù)是2099999999，并對21億以內的素數(shù)數(shù)量變化趨勢進行分析.

首先，看一下自然數(shù)1億到21億之間素數(shù)數(shù)量變化規(guī)律.圖2顯示了自然數(shù)每增加1億，這一億自然數(shù)之間對應的素數(shù)個數(shù).顯然素數(shù)個數(shù)隨著自然數(shù)的增加、因數(shù)相應增加，素數(shù)在每一億自然數(shù)區(qū)間內個數(shù)減少，即自然數(shù)每增加1億，在這新增加的1億自然數(shù)中所包含的素數(shù)個數(shù)是在遞減的（圖2），因此有了文章一開始的疑問：隨著自然數(shù)增大素數(shù)個數(shù)會減少，是否在自然數(shù)大于某個數(shù)后，素數(shù)個數(shù)增加值為零呢？也就是說素數(shù)似乎應該有個尾？

其次，再來看一下隨著自然數(shù)的增加對應的素數(shù)總數(shù)增量關系.在圖2的線性坐標系中顯示的素數(shù)個數(shù)在每一億自然數(shù)區(qū)間非線性減少，具有漸近X軸趨勢，似乎是一種無限接近而又不能到達X軸，因此在雙對數(shù)坐標系中查看二者關系有什么變化趨勢.圖3顯示了素數(shù)總數(shù)-自然數(shù)在雙對數(shù)坐標系中非線性變化關系：自然數(shù)每增加一個數(shù)量級（10倍），小于這個自然數(shù)的所有素數(shù)總個數(shù)也增加若干倍，但素數(shù)增加倍數(shù)小于10（表1），且二者呈非線性關系增加（圖3），由于二者關系曲線在Y=X曲線下方，顯然素數(shù)增加的速度小于自然數(shù)，而且曲線呈下凸特征，沒有漸近水平趨勢，即素數(shù)總個數(shù)沒有趨于某一上限趨勢，也就是說素數(shù)總數(shù)將會隨著自然數(shù)增加而無限增加下去.表1中自然數(shù)按10倍比例關系繼續(xù)增加下去可以構成一組比例為10的等比正項級數(shù)數(shù)列.隨著自然數(shù)的10倍關系增加素數(shù)總個數(shù)呈大于6倍的比例關系增加，而且隨著自然數(shù)的增加，素數(shù)增加的倍數(shù)也在增大，且有漸近10的趨勢（表1），當然其增加的比例關系上限不可能超過自然數(shù)增加的倍數(shù)10，即圖3中素數(shù)曲線有接近Y=X曲線趨勢但不會超越.

差值素數(shù)倍數(shù)大10倍而增加的倍數(shù)素數(shù)總數(shù)隨自然數(shù)擴最大素數(shù)值素數(shù)總個數(shù)最大自然數(shù)

3.結論

通過上述分析可知，由自然數(shù)和素數(shù)的總個數(shù)可組成自然數(shù)、素數(shù)兩個數(shù)列，即表1中的自然數(shù)、素數(shù)個數(shù)項所組成的數(shù)列，自然數(shù)數(shù)列以10倍的關系無限增加下去，相應的素數(shù)總個數(shù)所組成的數(shù)列呈大于6倍的關系相應的增加下去，根據(jù)達朗貝爾正項級數(shù)比值審斂判別法可知：由自然數(shù)、素數(shù)的個數(shù)所構成的2個正項級數(shù)都是發(fā)散的.故素數(shù)將隨著自然數(shù)的增加而不斷的增多，即素數(shù)沒有盡頭.

此次利用計算機算出的約1億個素數(shù)中最大一個素數(shù)是2099999999.

【參考文獻】

[ 1 ]魏貴民.高等數(shù)學[M].北京：地質出版社，1999.

[ 2 ]王云葵，馬武瑜.關于判別素數(shù)的充要條件[J].延安大學學報.2001，20（1），18-20.

[ 3 ]崔彩霞.素數(shù)判定算法分析.教學管理[J].2001.12，75.

[ 4 ]趙改換.關于正整數(shù)數(shù)列中素數(shù)的分布規(guī)律[J].洛陽師專學報.2000，19（2），33-35.