素?cái)?shù)極限問(wèn)題探討

付媛媛　錢(qián)俊彤　錢(qián)冠州　馬銘里

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

【關(guān)鍵詞】素?cái)?shù)；自然數(shù)；因數(shù)

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

1.素?cái)?shù)的算法

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

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

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

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

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

2.計(jì)算結(jié)果分析

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

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

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

差值素?cái)?shù)倍數(shù)大10倍而增加的倍數(shù)素?cái)?shù)總數(shù)隨自然數(shù)擴(kuò)最大素?cái)?shù)值素?cái)?shù)總個(gè)數(shù)最大自然數(shù)

3.結(jié)論

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

此次利用計(jì)算機(jī)算出的約1億個(gè)素?cái)?shù)中最大一個(gè)素?cái)?shù)是2099999999.

【參考文獻(xiàn)】

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

[ 2 ]王云葵，馬武瑜.關(guān)于判別素?cái)?shù)的充要條件[J].延安大學(xué)學(xué)報(bào).2001，20（1），18-20.

[ 3 ]崔彩霞.素?cái)?shù)判定算法分析.教學(xué)管理[J].2001.12，75.

[ 4 ]趙改換.關(guān)于正整數(shù)數(shù)列中素?cái)?shù)的分布規(guī)律[J].洛陽(yáng)師專學(xué)報(bào).2000，19（2），33-35.