素數極限問題探討

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

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

【關鍵詞】素數；自然數；因數

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

1.素數的算法

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

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

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

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

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

2.計算結果分析

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

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

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

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

3.結論

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

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

【參考文獻】

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

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

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

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