質數表演算法

1. 什麼是質數

質數(又稱為素數）
1.就是在所有比1大的整數中，除了1和它本身以外，不再有別的因數，這種整數叫做質數。還可以說成質數只有1和它本身兩個約數。2.素數是這樣的整數，它除了能表示為它自己和1的乘積以外，不能表示為任 何其它兩個整數的乘積。例如，15＝3＊5，所以15不是素數；
又如，12 ＝6＊2＝4＊3，所以12也不是素數。另一方面，13除了等於13＊1以 外，不能表示為其它任何兩個整數的乘積，所以13是一個素數。
[編輯本段]質數的概念
一個數，如果只有1和它本身兩個因數，這樣的數叫做質數（或素數）。例如 2，3，5，7 是質數，而 4，6，8，9 則不是，後者稱為合成數或合數。從這個觀點可將整數分為兩種，一種叫質數，一種叫合成數。（1不是質數，也不是合數）著名的高斯「唯一分解定理」說，任何一個整數。可以寫成一串質數相乘的積。質數中除2是偶數外，其他都是奇數。
[編輯本段]質數的奧秘
質數的分布是沒有規律的，往往讓人莫名其妙。如：101、401、601、701都是質數，但上下面的301（7*43）和901（17*53）卻是合數。
有人做過這樣的驗算：1^2+1+41=43,2^2+2+41=47,3^2+3+41=53……於是就可以有這樣一個公式：設一正數為n，則n^2+n+41的值一定是一個質數。這個式子一直到n=39時，都是成立的。但n=40時，其式子就不成立了，因為40^2+40+41=1681=41*41。
說起質數就少不了哥德巴赫猜想，和著名的「1+1」
哥德巴赫猜想 ：(Goldbach Conjecture)
內容為「所有的不小於6的偶數，都可以表示為兩個素數」
這個問題是德國數學家哥德巴赫（C．Goldbach，1690-1764）於1742年6月7日在給大數學家歐拉的信中提出的，所以被稱作哥德巴赫猜想。同年6月30日，歐拉在回信中認為這個猜想可能是真的，但他無法證明。從此，這道數學難題引起了幾乎所有數學家的注意。哥德巴赫猜想由此成為數學皇冠上一顆可望不可及的「明珠」。「用當代語言來敘述，哥德巴赫猜想有兩個內容，第一部分叫做奇數的猜想，第二部分叫做偶數的猜想。奇數的猜想指出，任何一個大於等於7的奇數都是三個素數的和。偶數的猜想是說，大於等於4的偶數一定是兩個素數的和。」（引自《哥德巴赫猜想與潘承洞》）
哥德巴赫猜想貌似簡單，要證明它卻著實不易，成為數學中一個著名的難題。18、19世紀，所有的數論專家對這個猜想的證明都沒有作出實質性的推進，直到20世紀才有所突破。直接證明哥德巴赫猜想不行，人們採取了「迂迴戰術」，就是先考慮把偶數表為兩數之和，而每一個數又是若干素數之積。如果把命題"每一個大偶數可以表示成為一個素因子個數不超過a個的數與另一個素因子不超過b個的數之和"記作"a＋b"，那麼哥氏猜想就是要證明"1＋1"成立。
1900年，20世紀最偉大的數學家希爾伯特，在國際數學會議上把「哥德巴赫猜想」列為23個數學難題之一。此後，20世紀的數學家們在世界范圍內「聯手」進攻「哥德巴赫猜想」堡壘，終於取得了輝煌的成果。
到了20世紀20年代，有人開始向它靠近。1920年，挪威數學家布爵用一種古老的篩選法證明，得出了一個結論：每一個比6大的偶數都可以表示為（9+9）。這種縮小包圍圈的辦法很管用，科學家們於是從（9十9）開始，逐步減少每個數里所含質數因子的個數，直到最後使每個數里都是一個質數為止，這樣就證明了「哥德巴赫猜想」。
1920年，挪威的布朗(Brun)證明了 「9+9 」。
1924年，德國的拉特馬赫(Rademacher)證明了「7+7 」。
1932年，英國的埃斯特曼(Estermann)證明了 「6+6 」。
1937年，義大利的蕾西(Ricei)先後證明了「5+7 」, 「4+9 」, 「3+15 」和「2+366 」。
1938年，蘇聯的布赫 夕太勃(Byxwrao)證明了「5+5 」。
1940年，蘇聯的布赫 夕太勃(Byxwrao)證明了 「4+4 」。
1948年，匈牙利的瑞尼(Renyi)證明了「1+c 」，其中c是一很大的自然數。
1956年，中國的王元證明了 「3+4 」。
1957年，中國的王元先後證明了 「3+3 」和 「2+3 」。
1962年，中國的潘承洞和蘇聯的巴爾巴恩(BapoaH)證明了 「1+5 」， 中國的王元證明了「1+4 」。
1965年，蘇聯的布赫 夕太勃(Byxwrao)和小維諾格拉多夫(BHHopappB)，及 義大利的朋比利(Bombieri)證明了「1+3 」。
1966年，中國的陳景潤證明了 「1+2 」[用通俗的話說，就是大偶數=素數+素數*素數或大偶數=素數+素數（註：組成大偶數的素數不可能是偶素數，只能是奇素數。因為在素數中只有一個偶素數，那就是2。）]。
其中「s + t 」問題是指: s個質數的乘積 與t個質數的乘積之和
20世紀的數學家們研究哥德巴赫猜想所採用的主要方法，是篩法、圓法、密率法和三角和法等等高深的數學方法。解決這個猜想的思路，就像「縮小包圍圈」一樣，逐步逼近最後的結果。
由於陳景潤的貢獻，人類距離哥德巴赫猜想的最後結果「1＋1」僅有一步之遙了。但為了實現這最後的一步，也許還要歷經一個漫長的探索過程。有許多數學家認為，要想證明「1＋1」，必須通過創造新的數學方法，以往的路很可能都是走不通的。實際上：
一陳景潤證明的不是哥德巴赫猜想
陳景潤與邵品宗合著的【哥德巴赫猜想】第118頁（遼寧教育出版社）寫道：陳景潤定理的「1+1」結果，通俗地講是指：對於任何一個大偶數N,那麼總可以找到奇素數P',P",或者P1,P2,P3,使得下列兩式至少一式成立：「
N=P'+P" (A)
N=P1+P2*P3 (B)
當然並不排除(A)(B)同時成立的情形，例如62=43+19，62=7+5X11。」
眾所周知，哥德巴赫猜想是指對於大於4的偶數（A)式成立，【1+2】是指對於大於10的偶數（B)式成立，
兩者是不同的兩個命題，陳景潤把兩個毫不相關的命題混為一談，並在申報獎項時偷換了概念（命題），陳景潤也沒有證明【1+2】，因為【1+2】比【1+1】難得多。
二。 陳景潤使用了錯誤的推理形式
陳採用的是相容選言推理的「肯定肯定式」：或者A，或者B，A，所以或者A或B，或A與B同時成立。 這是一種錯誤的推理形式，模稜兩可，牽強附會，言之無物，什麼也沒有肯定，正如算命先生那樣「：李大嫂分娩，或者生男孩，或者生女孩，或者同時生男又生女（多胎）」。無論如何都是對的，這種判斷在認識論上稱為不可證偽，而可證偽性是科學與偽科學的分界。相容選言推理只有一種正確形式。否定肯定式：或者A，或者B，非A，所以B。相容選言推理有兩條規則：1，否認一部分選言肢，就必須肯定另一部分選言肢；2，肯定一部分選言肢卻不能否定另一部份選言肢。可見對陳景潤的認可表明中國數學會思維混亂，缺乏基本的邏輯訓練。
三。 陳景潤大量使用錯誤概念
陳在論文中大量使用「充分大」和「殆素數」這兩個含糊不清的概念。而科學概念的特徵就是：精確性，專義性，穩定性，系統性，可檢驗性。「殆素數」指很像素數，拿像與不像來論證，這是小孩的游戲。而「充分大」，陳指10的50萬次方，這是不可檢驗的數。
四。陳景潤的結論不能算定理
陳的結論採用的是特稱（某些，一些），即某些N是(A)，某些N是（B)，就不能算定理，因為所有嚴格的科學的定理，定律都是以全稱（所有，一切，全部，每個）命題形式表現出來，一個全稱命題陳述一個給定類的所有元素之間的一種不變關系，適用於一種無窮大的類，它在任何時候都無區別的成立。而陳景潤的結論，連概念都算不上。
五。陳景潤的工作嚴重違背認識規律
在沒有找到素數普篇公式之前，哥氏猜想是無法解決的，正如化圓為方取決於圓周率的超越性是否搞清，事物質的規定性決定量的規定性。（王曉明1999年《中華傳奇》第三期「哥德巴赫猜想傳奇）
[編輯本段]「質數」——Prime Number的幾種英文解釋
1.In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. Or for short: A prime number is a natural number with exactly two natural divisors. A natural number that is greater than one and is not a prime is called a composite number. The numbers zero and one are neither prime nor composite. The property of being a prime is called primality. Prime numbers are of fundamental importance in number theory. [From Wikipedia]
2.A whole number not divisible without a remainder by any whole number other than itself and one.（漢譯：素數，質數：只能被其本身和一整除而沒有餘數的整數）[From American Heritage Dictionary]
3.any integer other than 0 or ± 1 that is not divisible without remainder by any other integers except ± 1 and ± the integer itself. [From The Merriam-Webster's Collegiate® Dictionary]
4.a number that can be divided only by itself and the number one. For example, three and seven are prime numbers.[From Longman Dictionary of Contemporary English]
[編輯本段]質數的性質
被稱為「17世紀最偉大的法國數學家」費爾馬，也研究過質數的性質。他發現，設Fn=2^(2^n)+1，則當n分別等於0、1、2、3、4時，Fn分別給出3、5、17、257、65537，都是質數，由於F5太大（F5=4294967297），他沒有再往下檢測就直接猜測：對於一切自然數，Fn都是質數。但是，就是在F5上出了問題！費爾馬死後67年，25歲的瑞士數學家歐拉證明：F5=4294967297=641*6700417，並非質數，而是合數。
更加有趣的是，以後的Fn值，數學家再也沒有找到哪個Fn值是質數，全部都是合數。目前由於平方開得較大，因而能夠證明的也很少。現在數學家們取得Fn的最大值為：n=1495。這可是個超級天文數字，其位數多達10^10584位，當然它盡管非常之大，但也不是個質數。質數和費爾馬開了個大玩笑！
還有一種被稱為「殆素數」的，意思是很像素數，著名數學家陳景潤就使用了這個概念，他的「1+2」的「2」，就表示「殆素數」，實際上是一個合數。大家不要搞混了。嚴格地講，「殆素數」不是一個科學概念，因為科學概念的特徵是（1）精確性；（2）穩定性；（3）可以檢驗；（4）系統性；（5）專義性。例如，許多數學家使用了「充分大」，這也是一個模糊概念，因為陳景潤把它定義為「10的50萬次方」，即在10的後面加上50萬個「0」。這是一個無法檢驗的數。
[編輯本段]質數的假設
17世紀還有位法國數學家叫梅森，他曾經做過一個猜想：2^p-1代數式，當p是質數時，2^p-1是質數。他驗算出了：當p=2、3、5、7、17、19時，所得代數式的值都是質數，後來，歐拉證明p=31時，2^p-1是質數。 p＝2，3，5，7時，Mp都是素數，但M11＝2047＝23×89不是素數。
還剩下p=67、127、257三個梅森數，由於太大，長期沒有人去驗證。梅森去世250年後，美國數學家科勒證明，2^67-1=193707721*761838257287，是一個合數。這是第九個梅森數。20世紀，人們先後證明：第10個梅森數是質數，第11個梅森數是合數。質數排列得這樣雜亂無章，也給人們尋找質數規律造成了困難。
[編輯本段]質數表上的質數
現在，數學家找到的最大的梅森數是一個有9808357位的數：2^32582657-1。數學雖然可以找到很大的質數，但質數的規律還是無法循通。
300以內的質數表
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
53 59 61 67 71 73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173 179 181 191 193 197
199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
283 293 [編輯本段]【求大質數的方法】
研究發現質數除2以外都是奇數，而奇數除了【奇數*奇數】(或再加「*奇數」）都是質數。那麼用計算機先把【奇數*奇數】(或再加「*奇數」）（比如9，15，21，25，27，33，35，39……）都求出來，再找奇數中上面沒提到的那些數，那些數就是素數。
人們找出的幾個超大質數中有遺漏，那麼就可以用此方法求出那些遺漏的數，不過需要很長時間！
這對於「孿生素數」有幫助喔！
上面這個演算法比較垃圾，對於求很大的素數效率低下，這個很大的素數可以用概率演算法求。
求素數，請用《公理與素數計算》。這種方法用不著將所有奇數都寫出來，而且計算出來的素數可以做到一個不漏。對於合數的刪除，也不是涉及所有奇合數，刪除是准確無誤的，刪除奇合數後剩餘的全部是素數。如：對奇素數3的倍數的數進行刪除，在整個自然數中只須刪除一個數；對素數5的倍數的數進行刪除，在整個自然數中只須刪除2個數；對素數7的倍數的數進行刪除，在整個自然數中只須刪除8個數；以此類推，如果哪位老師能夠將它用電腦編成程序，對計算素數有很大的幫助。
[編輯本段]【質數的個數】
有近似公式： x 以內質數個數約等於 x / ln(x)
ln是自然對數的意思。
尚准確的質數公式未給出。
10 以內共 4 個質數。
100 以內共 25 個質數。
1000 以內共 168 個質數。
10000 以內共 1229 個質數。
100000 以內共 9592 個質數。
1000000 以內共 78498 個質數。
10000000 以內共 664579 個質數。
100000000 以內共 5761455 個質數。
......
總數無限。
[編輯本段]【求質數的方法】
古老的篩法可快速求出100000000以內的所有素數。
篩法，是求不超過自然數N（N＞1）的所有質數的一種方法。據說是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）發明的，又稱埃拉托斯特尼篩子。
具體做法是：先把N個自然數按次序排列起來。1不是質數，也不是合數，要劃去。第二個數2是質數留下來，而把2後面所有能被2整除的數都劃去。2後面第一個沒劃去的數是3，把3留下，再把3後面所有能被3整除的數都劃去。3後面第一個沒劃去的數是5，把5留下，再把5後面所有能被5整除的數都劃去。這樣一直做下去，就會把不超過N的全部合數都篩掉，留下的就是不超過N的全部質數。因為希臘人是把數寫在塗臘的板上，每要劃去一個數，就在上面記以小點，尋求質數的工作完畢後，這許多小點就像一個篩子，所以就把埃拉托斯特尼的方法叫做「埃拉托斯特尼篩」，簡稱「篩法」。（另一種解釋是當時的數寫在紙草上，每要劃去一個數，就把這個數挖去，尋求質數的工作完畢後，這許多小洞就像一個篩子。）

2. 1—1O000000000O0以內的質數表

1到10的12次方范圍內的質數表可以建立，但是數量很大，不便於查詢。

因此，一般都通過軟體工具或程序代碼進行判定。

寫了一段fortran代碼，可以快速判定18位以內的正整數的是否質數。

具體演算法見綠色部分的注釋。代碼很簡潔，效率僅次於埃氏篩法。8位大整數，判定過程不超過1秒。演算法可以用來計算和製作質數表，只不過題主要求的表過於龐大，保存到硬碟上大約是一個30G的文件。

附：計算實例和fortran程序代碼。

3. 生成有 100000 個質數的質數表的較快演算法用c++和方法

#include<cstdio>
#include<cstring>
constintmaxm=1100000;
constintmaxn=10010;
intcnt;
intPrime[maxn];
boolno_prime[maxm];
intmain(){
freopen("prime.out","w",stdout);
for(inti=2;cnt<10000;i++){
if(!no_prime[i])
Prime[++cnt]=i;
for(intj=1;j<=cnt&&Prime[j]*i<maxm;j++){
no_prime[Prime[j]*i]=true;
if(i%Prime[j]==0)break;
}
}
for(inti=1;i<=cnt;i++)
printf("%d",Prime[i]);
return0;
}

這是線性篩質數法，時間復雜度是O(n) 其中n是數據范圍

4. 生成素數表的演算法有哪些

篩選法求素數表，最快的素數表生成演算法。
所謂「篩選法」指的是「埃拉托色尼(Eratosthenes)篩法」。他是古希臘的著名數學家。他採取的方法是，在一張紙上寫上1到100全部整數，然後逐個判斷它們是否是素數，找出一個非素數，就把它挖掉，最後剩下的就是素數。
具體做法如下：
<1>
先將1挖掉(因為1不是素數)。
<2>
用2去除它後面的各個數，把能被2整除的數挖掉，即把2的倍數挖掉。
<3>
用3去除它後面的各數，把3的倍數挖掉。
<4>
分別用4、5…各數作為除數去除這些數以後的各數。這個過程一直進行到在除數後面的數已全被挖掉為止。例如找1～50的素數，要一直進行到除數為47為止（事實上，可以簡化，如果需要找1～n范圍內素數表，只需進行到除數為n^2(根號n)，取其整數即可。例如對1～50，只需進行到將50^2作為除數即可。）
如上演算法可表示為：
<1>
挖去1;
<2>
用剛才被挖去的數的下一個數p去除p後面各數，把p的倍數挖掉;
<3>
檢查p是否小於n^2的整數部分（如果n=1000,
則檢查p<31?），如果是，則返回(2)繼續執行，否則就結束;
<4>
紙上剩下的數就是素數。
參考鏈接：http://blog.chinaunix.net/uid-9078996-id-2010292.html

5. 什麼是素數呀,判斷是不是素數的演算法是什麼呀

素數只能被自身或1整除。

6. 判斷一個整數是不是素數的演算法

建立一個素數表（一般不大於此整數的算術平方根即可）進行試除，或者利用一些常見素數性質，以及被素數整除的性質來判斷

7. 誰由1000以內質數表

1000以內質數表如下：

質數表的 質數又稱 素數。指整數在一個大於1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。換句話說，只有兩個 正因數（1和自己）的自然數即為素數。比1大但不是素數的數稱為 合數。1和0既非素數也非合數。素數在 數論中有著很重要的地位。

(7)質數表演算法擴展閱讀：

質數表記憶口訣：

方法一：兒歌記憶法

（二、三、五、七 和 十一） （十三後面是十七） （十九、二三、二十九） （三一、三七、四十一） （四三、四七、五十三） （五九、六一、六十七） （七一、七三、七十九） （八三、八九、九十七）

方法二：口訣記憶法

二，三，五，七，一十一； 一三，一九，一十七； 二三，二九，三十七； 三一，四一，四十七； 四三，五三，五十九； 六一，七一，六十七； 七三，八三，八十九； 再加七九，九十七； 25個質數不能少； 百以內質數心中記。

二、質數的具體應用：

1、質數被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中（實為尋找素數的過程），將會因為找質數的過程（分解質因數）過久，使即使取得信息也會無意義。

2、在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數設計成質數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。

3、在害蟲的生物生長周期與殺蟲劑使用之間的關繫上，殺蟲劑的質數次數的使用也得到了證明。實驗表明，質數次數地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難產生抗葯性。

4、以質數形式無規律變化的導彈和魚雷可以使敵人不易攔截。

5、多數生物的生命周期也是質數（單位為年），這樣可以最大程度地減少碰見天敵的機會。