素數的定義 素數有關知識點

素數又叫質數(prime number)，有無限個。質數定義為在大于1的自然數中，除了1和它本身以外不再有其他因數。在一個大于1的數a和它的2倍之間必存在至少一個素數。一個偶數可以寫成兩個合數之和，其中每一個合數都最多只有9個質因數。

素數是什么

質數又稱素數。一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數（規定1既不是質數也不是合數）。

質數的個數是無窮的。歐幾里得的《幾何原本》中有一個經典的證明。它使用了證明常用的方法：反證法。具體證明如下：假設質數只有有限的n個，從小到大依次排列為p1，p2，……，pn，設N=p1×p2×……×pn。如果 為素數，則 要大于p1，p2，……，pn，所以它不在那些假設的素數集合中。如果N+1為合數，因為任何一個合數都可以分解為幾個素數的積；而N和N+1的最大公約數是1，所以不可能被p1，p2，……，pn整除，所以該合數分解得到的素因數肯定不在假設的素數集合中。因此無論該數是素數還是合數，都意味著在假設的有限個素數之外還存在著其他素數。所以原先的假設不成立。也就是說，素數有無窮多個。

素數相關知識點

1、素性檢測一般用于數學或者加密學領域。用一定的算法來確定輸入數是否是素數。不同于整數分解，素性測試一般不能得到輸入數的素數因子，只說明輸入數是否是素數。大整數的分解是一個計算難題，而素性測試是相對更為容易(其運行時間是輸入數字大小的多項式關系)。

2、素性測試通常是概率測試(不能給出100%正確結果)。這些測試使用除輸入數之外，從一些樣本空間隨機出去的數;通常，隨機素性測試絕不會把素數誤判為合數，但它有可能為把一個合數誤判為素數。

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