★題目

　　好，言歸正傳。下面俺就由淺入深，從各種角度來剖析這道題目的奧妙。
　　為了避免被人指責(zé)為"玩文字游戲"（有些同學(xué)自己審題不細(xì)，卻抱怨出題的人玩文字游戲），在介紹各種境界之前，再明確一下題意。
　　 前一個(gè)帖子 已經(jīng)介紹過，求質(zhì)數(shù)可以有如下2種玩法。

◇需求1

請實(shí)現(xiàn)一個(gè)函數(shù)，對于給定的整型參數(shù) N，該函數(shù)能夠把自然數(shù)中，小于 N 的質(zhì)數(shù)，從小到大打印出來。
比如，當(dāng) N = 10，則打印出
2 3 5 7

◇需求2

請實(shí)現(xiàn)一個(gè)函數(shù)，對于給定的整型參數(shù) N，該函數(shù)能夠從小到大，依次打印出自然數(shù)中最小的 N 個(gè)質(zhì)數(shù)。
比如，當(dāng) N = 10，則打印出
2 3 5 7 11 13 17 19 23 29

★試除法

　　首先要介紹的，當(dāng)然非"試除法"莫屬啦。考慮到有些讀者是菜鳥，稍微解釋一下。
　　"試除"，顧名思義，就是不斷地嘗試能否整除。比如要判斷自然數(shù) x 是否質(zhì)數(shù)，就不斷嘗試小于 x 且大于1的自然數(shù)，只要有一個(gè)能整除，則 x 是合數(shù)；否則，x 是質(zhì)數(shù)。
　　顯然，試除法是最容易想到的思路。不客氣地說，也是最平庸的思路。不過捏，這個(gè)最平庸的思路，居然也有好多種境界。大伙兒請看：

◇境界1

　　在試除法中，最最土的做法，就是：
　　假設(shè)要判斷 x 是否為質(zhì)數(shù)，就從 2 一直嘗試到 x-1。這種做法，其效率應(yīng)該是最差的。如果這道題目有10分，按照這種方式做出的代碼，即便正確無誤，俺也只給1分。

◇境界2

　　稍微聰明一點(diǎn)點(diǎn)的程序猿，會(huì)想：x 如果有（除了自身以外的）質(zhì)因數(shù)，那肯定會(huì)小于等于 x/2，所以捏，他們就從 2 一直嘗試到 x/2 即可。
　　這一下子就少了一半的工作量哦，但依然是很笨的辦法。打分的話，即便代碼正確也只有2分

◇境界3

　　再稍微聰明一點(diǎn)的程序猿，會(huì)想了：除了2以外，所有可能的質(zhì)因數(shù)都是奇數(shù)。所以，他們就先嘗試 2，然后再嘗試從 3 開始一直到 x/2 的所有奇數(shù)。
　　這一下子，工作量又少了一半哦。但是，俺不得不說，依然很土。就算代碼完全正確也只能得3分。

◇境界4

　　比前3種程序猿更聰明的，就會(huì)發(fā)現(xiàn)：其實(shí)只要從 2 一直嘗試到√ x ，就可以了。估計(jì)有些網(wǎng)友想不通了，為什么只要到√ x ?即可？
　　簡單解釋一下：因數(shù)都是成對出現(xiàn)的。比如，100的因數(shù)有：1和100，2和50，4和25，5和20，10和10?？闯鰜頉]有？成對的因數(shù)，其中一個(gè)必然小于等于100的開平方，另一個(gè)大于等于100的開平方。至于嚴(yán)密的數(shù)學(xué)證明，用小學(xué)數(shù)學(xué)知識(shí)就可以搞定，俺就不啰嗦了。

◇境界5

　　那么，如果先嘗試2，然后再針對 3 到√ x ?的所有奇數(shù)進(jìn)行試除，是不是就足夠優(yōu)了捏？答案顯然是否定的嘛？寫到這里，才剛開始熱身哦。
　　一些更加聰明的程序猿，會(huì)發(fā)現(xiàn)一個(gè)問題：嘗試從 3 到√ x ?的所有奇數(shù)，還是有些浪費(fèi)。比如要判斷101是否質(zhì)數(shù)，101的根號(hào)取整后是10，那么，按照境界4，需要嘗試的奇數(shù)分別是：3，5，7，9。但是你發(fā)現(xiàn)沒有，對9的嘗試是多余的。不能被3整除，必然不能被9整除......順著這個(gè)思路走下去，這些程序猿就會(huì)發(fā)現(xiàn)：其實(shí)，只要嘗試小于√ x ?的 質(zhì)數(shù) 即可。而這些質(zhì)數(shù)，恰好前面已經(jīng)算出來了（是不是覺得很妙？）。
　　所以，處于這種境界的程序猿，會(huì)把已經(jīng)算出的質(zhì)數(shù)，先保存起來，然后用于后續(xù)的試除，效率就大大提高了。
　　順便說一下，這就是算法理論中經(jīng)常提到的： 以空間換時(shí)間 。

◇補(bǔ)充說明

　　開頭的4種境界，基本上是依次遞進(jìn)的。不過，境界5跟境界4，是平級(jí)的。在俺考察過的應(yīng)聘者中，有人想到了境界4但沒有想到境界5；反之，也有人想到境界5但沒想到境界4。通常，這兩種境界只要能想到其中之一，俺會(huì)給5-7分；如果兩種都想到了，俺會(huì)給8-10分。
　　對于俺要招的"初級(jí)軟件工程師"的崗位，能同時(shí)想到境界4和境界5，應(yīng)該就可以了。如果你對自己要求不高，僅僅滿足于淺嘗輒止。那么，看到這兒，你就可以打住了，無需再看后續(xù)的內(nèi)容；反之，如果你比較好奇或者希望再多學(xué)點(diǎn)東西，請接著往下看。

★篩法

　　說完"試除法"，再來說說篩法（維基百科的解釋在" 這里 "）。俺不妨揣測一下：本文的讀者，應(yīng)該有2/3以上，從來沒有聽說過篩法。所以捏，順便跟大伙兒扯扯蛋，聊一下篩法的淵源。
　　這個(gè)篩法啊，真的是一個(gè)既巧妙又快速的求質(zhì)數(shù)方法。其發(fā)明人是公元前250年左右的一位希臘大牛—— 埃拉托斯特尼 。為啥說他是大牛捏？因?yàn)樗救司ǘ鄠€(gè)學(xué)科和領(lǐng)域，至少包括：數(shù)學(xué)、天文學(xué)、地理學(xué)（地理學(xué)這個(gè)詞匯，就是他創(chuàng)立的）、歷史學(xué)、文學(xué)（他是一個(gè)詩人）。真的堪稱"跨領(lǐng)域的大牛"。
　　他最讓俺佩服的是：僅僅用簡單的幾何方法，測量出了地球的周長、地球與月亮的距離、地球與太陽的距離、赤道與黃道的夾角......而且，這些計(jì)算結(jié)果跟當(dāng)代科學(xué)家測出的，相差無幾。要知道他生活的年代，大概相當(dāng)于中國的春秋戰(zhàn)國。而咱們的老祖宗，一直到明朝還頑固地堅(jiān)信：天是圓的、地是方的、月亮?xí)惶旃方o吃嘍......
　　好了，扯蛋完畢，言歸正傳。
　　估計(jì)很多人把篩法僅僅看成是一種具體的方法。其實(shí)， 篩法還是一種很普適的思想 。在處理很多復(fù)雜問題的時(shí)候，都可以看到篩法的影子。那么，篩法如何求質(zhì)數(shù)捏，說起來很簡單：
　　首先，2是公認(rèn)最小的質(zhì)數(shù)，所以，先把所有2的倍數(shù)去掉；然后剩下的那些大于2的數(shù)里面，最小的是3，所以3也是質(zhì)數(shù)；然后把所有3的倍數(shù)都去掉，剩下的那些大于3的數(shù)里面，最小的是5，所以5也是質(zhì)數(shù)......
　　上述過程不斷重復(fù)，就可以把某個(gè)范圍內(nèi)的合數(shù)全都除去（就像被篩子篩掉一樣），剩下的就是質(zhì)數(shù)了。維基百科上有一張很形象的動(dòng)畫，能直觀地體現(xiàn)出篩法的工作過程。


　　明白了"篩法"的原理，大伙兒應(yīng)該看出，篩法在速度上是明顯優(yōu)于"試除法"的。當(dāng)然，篩法的程序?qū)崿F(xiàn)也分為不同的境界。而且，篩法可講究的門道更多了。下面，俺分別從不同角度，聊一聊篩法都有哪些講究。

◇如何確定質(zhì)數(shù)的分布范圍？

　　這是采用篩法首先會(huì)碰到的問題。文本開頭給出的那兩種需求，其處理的方式完全不同，俺分別說一下。

需求1
　　對于需求1，這個(gè)自然不是問題。因?yàn)樵谛枨?中，質(zhì)數(shù)的分布范圍就是 N，已經(jīng)給出了，很好辦。

需求2
　　但是對于需求2，就難辦了。因?yàn)樾枨?給出的 N，表示需要打印的質(zhì)數(shù)的個(gè)數(shù)，那么這 N 個(gè)質(zhì)數(shù)會(huì)分布在多大的范圍捏？這可是個(gè)頭疼的問題啊。
　　但是，來應(yīng)聘的程序猿如果足夠牛的話，當(dāng)然不會(huì)被這個(gè)問題難倒。因?yàn)樗財(cái)?shù)的分布，是有規(guī)律可循滴——這就是大名鼎鼎的 素?cái)?shù)定理 。
　　稍微懂點(diǎn)數(shù)學(xué)的，應(yīng)該知道素?cái)?shù)的分布是越往后越稀疏。或者說，素?cái)?shù)的密度是越來越低。而素?cái)?shù)定理，說白了就是數(shù)學(xué)家找到了一些公式，用來估計(jì)某個(gè)范圍內(nèi)的素?cái)?shù)，大概有幾個(gè)。在這些公式中，最簡潔的就是? x/ln(x) ，公式中的 ln 表示自然對數(shù)（估計(jì)很多同學(xué)已經(jīng)忘了啥叫自然對數(shù)）。假設(shè)要估計(jì)1,000,000以內(nèi)有多少質(zhì)數(shù)，用該公式算出是72,382個(gè)，而實(shí)際有78,498個(gè)，誤差約8個(gè)百分點(diǎn)。該公式的特點(diǎn)是：估算的范圍越大，偏差率越小。
　　有了素?cái)?shù)定理，就可以根據(jù)要打印的質(zhì)數(shù)個(gè)數(shù)，反推出這些質(zhì)數(shù)分布在多大的范圍內(nèi)。因?yàn)檫@個(gè)質(zhì)數(shù)分布公式有一定的誤差（通常小于15%）。為了保險(xiǎn)起見，把反推出的素?cái)?shù)分布范圍再稍微擴(kuò)大15%，應(yīng)該就足夠了。

　　可能有同學(xué)會(huì)質(zhì)疑俺：誰有這么好的記性，能夠在筆試過程中背出這些質(zhì)數(shù)分布公式捏？
　　俺覺得：背不出來是正常滴。但是，對于有一定數(shù)學(xué)功底的應(yīng)聘者，假如他/她知道質(zhì)數(shù)分布公式，即便不能完整寫出來，只要在答題中體現(xiàn)出："此處通過質(zhì)數(shù)分布公式推算范圍"，那么俺也是認(rèn)可滴。
　　再啰嗦一次：關(guān)鍵是看idea！

◇如何設(shè)計(jì)存儲(chǔ)容器？

　　知道了分布范圍，接下來就得構(gòu)造一個(gè)容器，來存儲(chǔ)該范圍內(nèi)的所有自然數(shù)；然后在篩的過程中，把合數(shù)篩掉。那么，這個(gè)容器該如何設(shè)計(jì)捏？不同層次的程序猿，自然設(shè)計(jì)出來的容器也不同啦。

境界1
　　照例先說說最土的搞法——直接構(gòu)造一個(gè)整型的容器。在篩的過程中把發(fā)現(xiàn)的合數(shù)刪除掉，最后容器中就只剩下質(zhì)數(shù)了。
　　為啥說這種搞法最土捏？
　　首先，整型的容器，浪費(fèi)內(nèi)存空間。比方說，你用的是32位的C/C++或者是Java，那么每個(gè) int 都至少用掉4個(gè)字節(jié)的內(nèi)存。當(dāng) N 很大時(shí)，內(nèi)存開銷就成問題了。
　　其次，當(dāng) N 很大時(shí)，頻繁地對一個(gè)大的容器進(jìn)行刪除操作可能會(huì)導(dǎo)致頻繁的內(nèi)存分配和釋放（具體取決于容器的實(shí)現(xiàn)方式）；而頻繁的內(nèi)存分配/釋放，會(huì)導(dǎo)致明顯的CPU占用并可能造成內(nèi)存碎片。

境界2
　　為了避免境界1導(dǎo)致的弊端，更聰明的程序猿會(huì)構(gòu)造一個(gè)定長的布爾型容器（通常用數(shù)組）。比方說，質(zhì)數(shù)的分布范圍是1,000,000，那么就構(gòu)造一個(gè)包含1,000,000個(gè)布爾值的數(shù)組。然后把所有元素都初始化為 true。在篩的過程中，一旦發(fā)現(xiàn)某個(gè)自然數(shù)是合數(shù)，就以該自然數(shù)為下標(biāo)，把對應(yīng)的布爾值改為 false。
　　全部篩完之后，遍歷數(shù)組，找到那些值為 true 的元素，把他們的下標(biāo)打印出來即可。
　　此種境界的好處在于：其一，由于容器是定長的，運(yùn)算過程中避免了頻繁的內(nèi)存分配/釋放；其二，在某些語言中，布爾型占用的空間比整型要小。比如C++的 bool 僅用1字節(jié)
注：C++標(biāo)準(zhǔn)（ISO/IEC 14882）沒有硬性規(guī)定 sizeof(bool)==1，但大多數(shù)編譯器都實(shí)現(xiàn)為一字節(jié)。

境界3
　　雖然境界2解決了境界1的弊端，但還是有很大的優(yōu)化空間。有些程序猿會(huì)想出按位（bit）存儲(chǔ)的思路。這其實(shí)是在境界2的基礎(chǔ)上，優(yōu)化了空間性能。俺覺得：C/C++出身的或者是玩過匯編語言的，比較容易往這方面想。
　　以C++為例。一個(gè)bool占用1字節(jié)內(nèi)存。而1個(gè)字節(jié)有8個(gè)比特，每個(gè)比特可以表示0或1。所以，當(dāng)你使用按位存儲(chǔ)的方式，一個(gè)字節(jié)可以拿來當(dāng)8個(gè)布爾型使用。所以，達(dá)到此境界的程序猿，會(huì)構(gòu)造一個(gè)定長的byte數(shù)組，數(shù)組的每個(gè)byte存儲(chǔ)8個(gè)布爾值?？臻g性能相比境界2，提高8倍（對于C++而言）。如果某種語言使用4字節(jié)表示布爾型，那么境界3比境界2，空間利用率提高32倍。

★總結(jié)

　　看到俺寫"總結(jié)"二字，很多網(wǎng)友心想：總算看完了，知道該怎么求質(zhì)數(shù)才是最優(yōu)的了。
　　其實(shí)，你們又錯(cuò)了，本文才寫了不到一半。考慮到篇幅已經(jīng)有點(diǎn)長，而且俺打了這么多字，也有點(diǎn)累了，暫時(shí)剎住話匣子，下次接著聊。
　　希望看了今天這個(gè)介紹，大伙兒應(yīng)該明白一個(gè)道理：山外有山、天外有天。每一個(gè)技術(shù)領(lǐng)域里面的每一個(gè)細(xì)小的分支，深究下去都有很多的門道與奧妙。在你深究的過程中，必然會(huì)學(xué)到很多東西。深究的過程也就是你能力提高的過程。
　　本文后續(xù)的內(nèi)容，會(huì)介紹剛才提到的按位存儲(chǔ)法還有哪些缺陷，該如何解決。另外，還會(huì)介紹其它一些求質(zhì)數(shù)的方法。

總結(jié)

以上是生活随笔為你收集整理的寻找质数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。