2.1　素?cái)?shù)搜索

在進(jìn)行素?cái)?shù)搜索前，有必要清楚素?cái)?shù)有多少個(gè)，是有限個(gè)還是無(wú)窮多個(gè)。

對(duì)于這一問(wèn)題，兩千多年前的歐幾里得給出了以下明確的回答。

【命題】　素?cái)?shù)有無(wú)窮多個(gè)。

【證明】　下面用反證法證明。

假設(shè)素?cái)?shù)只有有限的n個(gè)，不妨設(shè)為p₁，p₂，…，p_n。

考察整數(shù)p＝p₁p₂…p_n＋1，無(wú)非以下兩種可能。

（1）整數(shù)p是合數(shù)。

如果整數(shù)p是合數(shù)，則p能被某一素?cái)?shù)q整除。

若素?cái)?shù)q是n個(gè)素?cái)?shù)p₁，p₂，…，p_n中的一個(gè)，則p₁p₂…p_n能被q整除，又p＝p₁p₂…p_n＋1能被q整除，因而1能被q整除，這顯然是不可能的。

若素?cái)?shù)q是n個(gè)素?cái)?shù)p₁，p₂，…，p_n以外的一個(gè)，則與假設(shè)矛盾。

（2）整數(shù)p是素?cái)?shù)。

顯然素?cái)?shù)p＝p₁p₂…p_n＋1大于p₁，p₂，…，p_n中的任何一個(gè)，是一個(gè)新的素?cái)?shù)，與假設(shè)矛盾。

因而得證素?cái)?shù)有無(wú)窮多個(gè)。

探討素?cái)?shù)，首先必須清楚哪些正整數(shù)是素?cái)?shù)，哪些正整數(shù)不是素?cái)?shù)。

搜索素?cái)?shù)的常用方法有試商判別法與厄拉多塞篩法兩種。這兩種方法各具特色，本節(jié)具體探討應(yīng)用這兩種方法搜索素?cái)?shù)。

2.1.1　試商判別法

試商判別法是依據(jù)素?cái)?shù)的定義來(lái)實(shí)施的。

試應(yīng)用試商判別法求出指定n位所有素?cái)?shù)，并統(tǒng)計(jì)n位素?cái)?shù)的個(gè)數(shù)。

1. 設(shè)計(jì)要點(diǎn)

應(yīng)用試商判別法來(lái)判別奇數(shù)k（只有唯一偶素?cái)?shù)2，不作試商判別）是不是素?cái)?shù)，只要逐一用奇數(shù)j（取3，5，…，直至）去試商。

若存在某個(gè)j能整除k，說(shuō)明k能被1與k本身以外的整數(shù)j整除，k不是素?cái)?shù)。

若上述范圍內(nèi)的所有奇數(shù)j都不能整除k，則k為素?cái)?shù)。

注意：有些程序把試商奇數(shù)j的取值上限定為k/2或k-1，這也是可行的，但并不是可取的，這樣無(wú)疑會(huì)增加許多試商的無(wú)效循環(huán)。

理論上說(shuō)，如果k存在一個(gè)大于且小于k的因數(shù)，則必存在一個(gè)與之對(duì)應(yīng)的小于且大于1的因數(shù)，因而從判別功能來(lái)說(shuō)，取到已足夠了。

判別j整除k，在C程序中常用表達(dá)式k%j＝＝0來(lái)實(shí)現(xiàn)。

2. 應(yīng)用試商判別法求n位素?cái)?shù)程序設(shè)計(jì)

3. 程序運(yùn)行示例與說(shuō)明

     請(qǐng)指定位數(shù)n(n>1):4
     1009　1013　1019　1021　1031　1033　1039　1049　1051　1061
     1063　1069　1087　1091　1093　1097　1103　1109　1117　1123
     ……
     9883　9887　9901　9907　9923　9929　9931　9941　9949　9967
     9973
     共1061個(gè)4位素?cái)?shù)。

從搜索結(jié)果可以看出，最小的4位素?cái)?shù)為1009，最大的4位素?cái)?shù)為9973，共有1061個(gè)4位素?cái)?shù)。

試商判別法簡(jiǎn)單直觀，設(shè)計(jì)容易實(shí)現(xiàn)，因此常為程序設(shè)計(jì)者所采用。

2.1.2　厄拉多塞篩法

搜索素?cái)?shù)，除了試商判別法之外，還有歷史更為悠久、效率更高的厄拉多塞篩法。本節(jié)簡(jiǎn)單介紹厄拉多塞篩法及其在搜索素?cái)?shù)上的應(yīng)用。

1. 厄拉多塞篩法簡(jiǎn)介

求素?cái)?shù)的篩法是公元前3世紀(jì)的厄拉多塞（Eratosthenes）提出來(lái)的：對(duì)于一個(gè)整數(shù)k，只要知道不超過(guò)的所有素?cái)?shù)p，劃去所有p的倍數(shù)2p，3p，…，剩下的整數(shù)就是不超過(guò)k的全部素?cái)?shù)。

【問(wèn)題】　試應(yīng)用厄拉多塞篩法求區(qū)間[100，200]中的素?cái)?shù)。

【探求】　分以下4步求解。

（1）首先求出不超過(guò)的所有奇素?cái)?shù)3，5，7，11，13，共5個(gè)。

（2）列出區(qū)間[100，200]中的所有奇數(shù)，共50個(gè)。

（3）在所列50個(gè)奇數(shù)中，分別劃去3的倍數(shù)、5的倍數(shù)、7的倍數(shù)、11的倍數(shù)與13的倍數(shù)（見圖2-1，分別以不同劃符標(biāo)記）。

圖2-1　應(yīng)用篩法求素?cái)?shù)劃去操作圖

（4）剩下沒(méi)有劃去的整數(shù)即為素?cái)?shù)。

通過(guò)以上劃去操作實(shí)施篩選，剩下以下整數(shù)為素?cái)?shù)。

即得區(qū)間[100，200]共有以上21個(gè)素?cái)?shù)。

2. 應(yīng)用篩法搜索素?cái)?shù)設(shè)計(jì)要點(diǎn)

為擴(kuò)大搜索范圍，相應(yīng)變量設(shè)置為double型。

（1）實(shí)施劃去操作。

應(yīng)用篩法求素?cái)?shù)，為了方便實(shí)施劃去操作，應(yīng)設(shè)置數(shù)組。

每一數(shù)組元素對(duì)應(yīng)一個(gè)待判別的奇數(shù)，并賦初值0。

如果該奇數(shù)為p的倍數(shù)，則應(yīng)劃去，于是對(duì)應(yīng)元素加一個(gè)劃去標(biāo)記，例如給該元素賦一個(gè)負(fù)數(shù)-1。最后，打印元素值不是-1（即沒(méi)有劃去）的元素對(duì)應(yīng)的奇數(shù)即所求素?cái)?shù)。

在指定區(qū)間[c，d]（約定c為奇數(shù)）上所有奇數(shù)表示為j＝c＋2k（k＝0，1，…，e，這里e＝（d-c）/2）。于是k＝（j-c）/2是奇數(shù)j在數(shù)組中的序號(hào)（下標(biāo)）。如果j為奇數(shù)的倍數(shù)，則對(duì)應(yīng)數(shù)組元素作劃去標(biāo)記，即a[（j-c）/2]＝-1。

（2）放寬劃去對(duì)象。

在實(shí)際應(yīng)用篩法的搜索過(guò)程中，p通常不一定取不超過(guò)的素?cái)?shù)，而是適當(dāng)放寬取不超過(guò)的奇數(shù)（從3開始）。這樣做盡管多了一些重復(fù)劃去操作，但省去了求不超過(guò)的素?cái)?shù)這一環(huán)節(jié)，程序?qū)崿F(xiàn)要簡(jiǎn)便些。

根據(jù)c與奇數(shù)i，確定g＝2?（floor（c/（2?i）））＋1，使得g?i接近區(qū)間下限c，從而使劃去的gi，（g＋2）i，…在[c，d]中，這樣可減少無(wú)效操作，提高對(duì)大區(qū)間的篩選效率。

最后，凡數(shù)組元素a[k]≠-1，則輸出對(duì)應(yīng)的奇數(shù)j＝c＋2?k即為素?cái)?shù)，并應(yīng)用變量n統(tǒng)計(jì)該區(qū)間的素?cái)?shù)個(gè)數(shù)。

3. 篩法求素?cái)?shù)程序設(shè)計(jì)

4. 程序運(yùn)行示例與說(shuō)明

     請(qǐng)輸入?yún)^(qū)間[c,d]的c,d(c>2):1480028120,1480028220
     1480028129　1480028141　1480028153　1480028159
     1480028171　1480028183　1480028189　1480028201
     1480028213
     共9個(gè)素?cái)?shù)。

這9個(gè)連續(xù)素?cái)?shù)（中間沒(méi)有其他素?cái)?shù)）在第10章中將會(huì)構(gòu)建一個(gè)3階素?cái)?shù)幻方。

篩法在較大區(qū)間的搜索與較大整數(shù)的判別上效率比試商判別法更高一些，但設(shè)計(jì)上較難把握。

運(yùn)行程序，輸入?yún)^(qū)間[10 000，99 999]，快捷輸出99 991等共8363個(gè)5位素?cái)?shù)。