質數

質數 （简体）

素數，又稱質數，一個大於1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數；即是只有兩個正因數（1和自己）的自然數。

比1大但不是質數的數稱之為合數又稱合成數，而1和0既非質數也非合數。質數的屬性稱為素性，質數在數論中有著非常重要的地位。

關於質數

最小的質數是2，也是質數中唯一偶數（雙數），其他都是奇數（單數）。質數有無限多個，所以並不存在最大的質數。

圍繞著質數存在很多數學問題、數學猜想、數學定理，較為著名的有孿生質數猜想、哥德巴赫猜想等等。

質數序列的開頭是這樣：

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)

質數集合有時也被表示成粗體 。

在抽象代數的一個分支－環論中，素元素有特殊的含義，在這個含義下，任何質數的加法的逆轉也是質數。換句話說，將整數Z的集合看成是一個環，-Z是一個素元素。不管怎樣，數學領域內，提到質數通常是指正質數。

算術基本定理說明每個大於1的正整數都可以寫成質數的乘積，並且這種乘積的形式是唯一的。因此質數也被稱為自然數的「建築的基石」。例如：

關於分解的詳細方法，可見於整數分解這條目。

這個定理的重要一點是，將1排斥在質數集合以外。如果1被認為是質數，那麼這些嚴格的闡述就不得不加上一些限制條件了。

0由於可以被任何數整除（因餘數一定等於0），所以它不符合素數的定義。

質數的數目

質數有無限多個。現在已知最古老的檢驗方法是歐幾里德在他的幾何原本中提出來的。該檢驗方法可以簡單地總結如下：

假設質數有限。將所有這些有限的質數相乘然後加1，會得到另一個數。此數無法被那些有限質數裡任何一個整除，無論除哪一個，總會餘1。如果該數為質數，則它不在一開始假設的質數集合中；如果該數為合數，因為任何一個合數都可以分解為質數之積，而一開始假設的質數都不能整除該合數，所以該合數分解得到的質因數不在一開始假設的質數集合中。因此無論該數是質數還是合數，都意味著在假設的有限個質數之外還存在其他質數，所以該假設不成立。也就是說，質數並非有限。對任何有限個質數的集合來說，永遠可以得到另一個質數不在該集合中，因此質數有無窮多個。

別的數學家也給出了他們自己的證明。歐拉證明了全部質數的倒數和發散到無窮的。恩斯特·庫默的證明尤其簡潔，Furstenberg用一般拓撲證明。

儘管整個質數是無窮的，仍然有人會問「100000以下有多少個質數?」，「一個隨機的100位數多大可能是質數?」。質數定理可以回答此問題。

尋找質數

尋找在給定限度內的質數排列，埃拉托斯特尼篩法是個很好的方法。然而在實際中，我們往往是想知道一個給定數是否是質數，而不是生成一個質數排列。進而，知道答案是很高的機率就是已經很滿意的了，用素性測試迅速地檢查一個給定數（例如，有幾千位數的長度）是否是質數是可能的。典型的方法是隨機選取一個數，然後圍繞著這個數和可能的質數N檢查一些方程式。重複這個過程幾次後，它宣布這個數是明顯的合數或者可能是質數。這種方法是不完美的：對某些測試而言，例如費馬測試，不論選取了多少隨機數都有可能將一些合數判斷成可能的質數，這就引出了另一種數偽質數。而像米勒-拉賓測試，雖然只要選取夠多數字來檢驗方程式，就可以保證其檢驗出的質數性是正確的，但這個保證門檻的數量太過龐大，甚至比試除法所需的還要多，在有限時間內運行起來只能知道答案正確的機率很高，不能保證一定正確。

目前最大的已知質數是2^43112609 − 1（此數字位長度是12978189），它是在2008年8月23日由GIMPS發現。這組織也在2008年9月6日發現了目前所知第二大的已知質數2^37156667 − 1（此數字位長度是11185272）。

數學家一直努力找尋產生質數的公式，但截至目前為止，並沒有一個基本函數或是多項式可以正確產生所有的質數。歷史上有許多試驗的例子：17世紀初法國數學家梅森(Mersenne)在他的一個著作當中討論了這樣一種我們現在稱之為梅森質數的質數，M_p=2^p - 1，本來以為只要p是一個質數，n = 2^p - 1就會是一個質數，這在p = 3，p = 5，p = 7都是正確的，但是p = 11時 }-就不是質數了。

質數演算法

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

• 根據質數分佈特性可以把數除以6，得其餘數（n為大於0, 小於((x 的平方根) /6)的正整數。）：

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

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

#include <iostream>
using namespace std;
 
const int LIMIT = 1000000;
 
int main()
{
	bool sieve[LIMIT+1];
	int p, j, p2;
 
	int nLIMIT = LIMIT -6;
	for (int i = 7 ; i <= nLIMIT ; i+=6)
	{
		sieve[i] = true;
		sieve[i+2] = false;
		sieve[i+4] = true;
	}
 
	p = 5;
	while ((j = p*p) <= LIMIT)
	{
		p2 = p << 1;
		while (j <= LIMIT)
		{
			sieve[j] = false;
			j += p2;
		}
 
		do
		{
			p += 2;
		} while (sieve[p] == false);
	}
 
 
	cout << "Prime numbers:\n";
	cout << "2,3,5";
 
	nLIMIT = LIMIT -4;
	for (int i = 7 ; i <= nLIMIT ; i += 2)
	{
		if (sieve[i]) cout << "," << i ;
		i+=4;
		if (sieve[i]) cout << "," << i ;
	}
 
	return 0;
}

檢驗質數

檢查一個正整數N是否為質數，最簡單的方法就是試除法，將該數N用小於等於的所有質數去試除，若均無法整除，則N為質數。

2002年，印度人 M. Agrawal 、N. Kayal 以及 N. Saxena 提出了 AKS 質數檢驗演算法，證明了可以在多項式時間內檢驗是否為質數。

未解之謎

• 哥德巴赫猜想：是否每個大於2的雙數均可寫成兩個質數之和？
• 孿生質數猜想：孿生質數就是差為2的質數對，例如11和13。是否存在無窮多的孿生質數？
• 斐波那契數列是否存在無窮多的質數？
• 是否存在無窮多梅森質數？
• 在n²與(n + 1)²之間每隔n就有一個質數？
• 是否存在無窮個形式如n² + 1的質數？
• 黎曼猜想

質數的應用

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

外部連結

• 素網
• Determinación geométrica de los números primos y perfectos

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History