質數怎應用?質數何用?

素數，又稱質數，一個大於1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數；即是只有兩個正因數（1和自己）的自然數。
比1大但不是素數的數稱之為合數又稱合成數，而1和0既非素數也非合數。素數的屬性稱為素性，素數在數論中有著非常重要的地位。





目錄[隱藏]

1 關於素數
2 素數的數目
3 尋找素數

3.1 質數算法
4 檢驗素數
5 未解之謎
6 素數的應用
7 外部連結



[編輯] 關於素數
最小的素數是2，也是素數中唯一偶數（雙數），其他都是奇數（單數）。而最大的素數並不存在，而且素數有無限個，這一點歐幾里德已在其《幾何原本》中證明。證明的思想很直接：如果存在一個最大的素數p，則素數的個數是有限的；這時，如果我們把所有的素數乘起來再加1，得到的自然數q（即：q = 2 * 3 * 5 * 7 * ... * p + 1）比p還要大。但q不能為任何比它小的素數整除（即不能被從2到p的任何素數整除），因此根據定義q必然也是素數。此時素數q比p還要大，這和假設“p為最大素數”相矛盾。因此不存在一個最大的素數。
圍繞素數存在很多的數學問題、數學猜想、數學定理，較為著名的有孿生素數猜想、哥德巴赫猜想等等。
素數序列的開頭是這樣：

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 (OEIS:A000040)
素數集合有時也被表示成粗體
圖片參考：http://upload.wikimedia.org/math/6/2/3/623709596363008e89cf20b6caba4df7.png
。
在抽象代數的一個分支－環論中，素元素有特殊的含義，在這個含義下，任何素數的加法的逆轉也是素數。換句話說，將整數Z的集合看成是一個環，-Z是一個素元素。不管怎樣，數學領域內，提到素數通常是指正素數。
算術基本定理說明每個大於1的正整數都可以寫成素數的乘積，並且這種乘積的形式是唯一的。因此素數也被稱為自然數的“建築的基石”。例如：


圖片參考：http://upload.wikimedia.org/math/f/7/a/f7a222e62c50d235f07cc90f8eda574e.png

關於分解的詳細方法，可見於整數分解這條目。
這個定理的重要一點是，將1排斥在素數集合以外。如果1被認為是素數，那麼這些嚴格的闡述就不得不加上一些限制條件了。
0由於可以被任何數整除（因餘數一定等於0），所以它不符合素數的定義。

[編輯] 素數的數目
素數是無窮多的，對這個論斷，現在所已知的最古老的檢驗方法是歐幾里德在他的幾何原本中提出來的。他的檢驗方法可以簡單地總結如下：

取有限個數的素數，因為要做自變量我們假設全部的素數都存在，將這些素數相乘然後加1，得到的數是不會被這些素數中的任何一個整除的，因為無論除哪個總會餘1。因此這個數要麼本身就是個素數，要麼存在不在這個有限集合內的約數。因此我們開始用的集合不包含所有的素數。
別的數學家也給出了他們自己的證明。歐拉證明瞭全部素數的倒數和發散到無窮的。恩斯特·庫默的證明尤其簡潔，Furstenberg用一般拓撲證明。
儘管整個素數是無窮的，仍然有人會問“100000以下有多少個素數?”，“一個隨機的100位數多大可能是素數?”。素數定理可以回答此問題。

[編輯] 尋找素數
尋找在給定限度內的素數排列，埃拉托斯特尼篩法法是個很好的方法。然而在實際中，我們往往是想知道一個給定數是否是素數，而不是生成一個素數排列。進而，知道答案是很高的概率就是已經很滿意的了，用素性測試迅速地檢查一個給定數（例如，有幾千位數的長度）是否是素數是可能的。典型的方法是隨機選取一個數，然後圍繞著這個數和可能的素數N檢查一些方程式。重複這個過程幾次後，它宣佈這個數是明顯的合數或者可能是素數。這種方法是不完美的：對某些測試而言，例如費馬測試，不論選取了多少隨機數都有可能將一些合數判斷成可能的素數，這就引出了另一種數偽素數。而像米勒-拉賓測試，雖然只要選取夠多數字來檢驗方程式，就可以保證其檢驗出的質數性是正確的，但這個保證門檻的數量太過龐大，甚至比試除法所需的
圖片參考：http://upload.wikimedia.org/math/f/c/8/fc8cf8ecadcb5507e227e1a5ea162599.png
還要多，在有限時間內運行起來只能知道答案正確的機率很高，不能保證一定正確。
目前最大的已知素數是232582657 − 1（此數字位長度是9,808,358），它是在2006年9月4日由GIMPS發現。這組織也在2005年12月15日發現了目前所知第二大的已知素數230402457 − 1（此數字位長度是9,152,052）。
數學家一直努力找尋產生素數的公式，但截至目前為止，並沒有一個基本函數或是多項式可以正確產生所有的素數。歷史上有許多試驗的例子：17世紀初法國數學家梅森(Mersenne)在他的一個著作當中討論了這樣一種我們現在稱之為梅森素數的素數，Mp=2p - 1，本來以為只要p是一個素數，n = 2p - 1就會是一個素數，這在p = 3，p = 5，p = 7都是正確的，但是p = 11時
圖片參考：http://upload.wikimedia.org/math/3/d/a/3dae1a2b36e0f1965952153d1dbe9e14.png
}-就不是素數了。

[編輯] 質數算法

欲求出小於x的所有質數……

根據質數分佈特性可以用



6n + 0……偶數（2的倍數）。
6n + 1……可能為質數？
6n + 2……偶數（2的倍數）。
6n + 3……3的倍數。
6n + 4……偶數（2的倍數）。
6n + 5……可能為質數？

n為大於0, 小於((x 的平方根) /6)的正整數

所以，如果預先排除了 2 與 3 的話……
那隻要算 6n + 1 與 6n + 5 是否為質數就好了。 這樣，搜尋範圍立刻少掉原本的2/3, 也比單單排除的偶數還少了1/3。