-
質數
鎖定
- 中文名
- 質數
- 外文名
- prime number
- 別 名
- 素數
- 討論範圍
- 非0自然數
- 定 義
- 只有1和它本身兩個因數的自然數
- 反義詞
- 合數
- 所屬範圍
- 自然數
質數簡介
質數又稱素數。一個大於1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數（規定1既不是質數也不是合數）。
質數的個數是無窮的。歐幾里得的《幾何原本》中有一個經典的證明。它使用了證明常用的方法：反證法。具體證明如下：假設質數只有有限的n個，從小到大依次排列為p1，p2，……，pn，設N=p1×p2×……×pn。如果
為素數，則
要大於p1，p2，……，pn，所以它不在那些假設的素數集合中。如果N+1為合數，因為任何一個合數都可以分解為幾個素數的積；而N和N+1的最大公約數是1，所以不可能被p1，p2，……，pn整除，所以該合數分解得到的素因數肯定不在假設的素數集合中。因此無論該數是素數還是合數，都意味着在假設的有限個素數之外還存在着其他素數。所以原先的假設不成立。也就是説，素數有無窮多個。
儘管整個素數是無窮的，仍然有人會問“100，000以下有多少個素數？”，“一個隨機的100位數多大可能是素數？”。素數定理可以回答此問題。
質數性質
1、質數p的約數只有兩個：1和p。
2、算術基本定理：任一大於1的自然數，要麼本身是質數，要麼可以分解為幾個質數之積，且這種分解是唯一的。
3、質數的個數是無限的。
4、質數的個數公式
是不減函數。
6、若n為大於或等於2的正整數，在n到
之間至少有一個質數。
7、在一個大於1的數a和它的2倍之間（即區間（a, 2a]中）必存在至少一個素數。
質數應用
質數被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中（實為尋找素數的過程），將會因為找質數的過程（分解質因數）過久，使即使取得信息也會無意義。
在害蟲的生物生長週期與殺蟲劑使用之間的關係上，殺蟲劑的質數次數的使用也得到了證明。實驗表明，質數次數地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難產生抗藥性。
以質數形式無規律變化的導彈和魚雷可以使敵人不易攔截。
多數生物的生命週期也是質數（單位為年），這樣可以最大程度地減少碰見天敵的機會。
質數編程
質數基本判斷思路
在一般領域，對正整數n，如果用2到
之間的所有整數去除，均無法整除，則n為質數。
質數代碼
Python 代碼：
from math import sqrt def is_prime(n): if n == 1: return False for i in range(2, int(sqrt(n))+1): if n % i == 0: return False return True
Java代碼：
1.
public static boolean testIsPrime2(int n){
if (n <= 3) {
return n > 1;
}
for(int i=2;i<n;i++){
if(n%i == 0)
return false;
}
return true;
}
/*優化後*/
public static boolean testIsPrime3(int n){
if (n <= 3) {
return n > 1;
}
for(int i=2;i<=Math.sqrt(n);i++){
if(n%i == 0)
return false;
}
return true;
}
2.
public class Prime {
public static void main（String[] args） {
int a = 17; //判斷17是不是質數
int c = 0;
for (int b = 2; b < a; b++) {
if (a % b != 0) {
c++;
}
}
if (c == a - 2) {
System.out.println(a + "是質數");
} else {
System.out.println(a + "不是質數");
}
}
}
Php代碼：
function isPrime($n) {//TurkHackTeam AVP production
if ($n <= 3) {
return $n > 1;
} else if ($n % 2 === 0 || $n % 3 === 0) {
return false;
} else {
for ($i = 5; $i * $i <= $n; $i += 6) {
if ($n % $i === 0 || $n % （$i + 2) === 0） {
return false;
}
}
return true;
}
}
C#代碼：
using System;
namespace 計算質數
{
class Program
{
static void Main(string[] args)
{
for (int i = 2,j=1; i < 2100000000&&j<=1000; i++)//輸出21億內的所有質數，j控制只輸出1000個。
{
if (st(i))
{
Console.WriteLine("{0,-10}{1}",j,i);
j++;
}
}
}
static bool st(int n)//判斷一個數n是否為質數
{
int m = (int)Math.Sqrt(n);
for(int i=2;i<=m;i++)
{
if(n%i==0 && i!=n)
return false;
}
return true;
}
}
}
C代碼：
#include <stdio.h>
#include <windows.h>
int main()
{
double x,y,i;
int a,b;
x = 3.0;
do{
i = 2.0;
do{
y = x / i;
a = (int)y;
if(y != a)//用於判斷是否為整數
{
if(i == x - 1)
{
b = (int)x;
printf("%d\n",b);
}
}
i++;
}while(y != a);
x++;
}while(x <= 10000.0);//3到10000的素數
system("pause");//防止閃退
return 0;
}
C/C++代碼：
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const long long size=100000;//修改size的數值以改變最終輸出的大小
long long zhishu[size/2];
void work (){//主要程序
zhishu[1]=2;
long long k=2;
for(long long i=3;i<=size;i++){//枚舉每個數
bool ok=1;
for(long long j=1;j<k;j++){//枚舉已經得到的質數
if(i%zhishu[j]==0){
ok=!ok;
break;
}
}
if（ok）{
zhishu[k]=i;
cout<<"count"<<k<<' '<<i<<endl;
k++;
}
}
}
int main（）{
freopen("zhishu.out","w",stdout);
cout<<"count1 2"<<endl;
work();
return 0;
}
bool isPrime(unsigned long n) {
if (n <= 3) {
return n > 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return false;
} else {
for (unsigned short i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % （i + 2） == 0) {
return false;
}
}
return true;
}
}
Pascal代碼：
function su(a:longint):boolean; var begin if a=2 then exit(true) else for i:=2 to trunc(sqrt(a))+1 do if a mod i=0 then exit（false）; exit(true); end.
Javascript代碼：
function isPrime(n) {
if (n <= 3) { return n > 1; }
if (n % 2 == 0 || n % 3 == 0) { return false; }
for (var i = 5; i * i <= n; i ++) {
if (n % i == 0 || n % (i + 1) == 0) { return false; }
}
return true;
}
Go代碼：
func isPrime(value int) bool {
if value <= 3 {
return value >= 2
}
if value%2 == 0 || value%3 == 0 {
return false
}
for i := 5; i*i <= value; i += 6 {
if value%i == 0 || value%（i+2） == 0 {
return false
}
}
return true
}
Basic 代碼
Private Function IfPrime（ByVal x As Long） As Boolean
Dim i As Long
If x < 0 Then x = -x
If x = 2 Then Return True
If x = 1 Then Return True
If x = 3 Then Return False
If x = 0 Then
MsgBox("error",,)
Return False
End If
For i = 2 To Int(Sqrt(x)) Step 1
If x Mod i = 0 Then Return False
Next i
Return True
End FunctionALGOL代碼
begin Boolean array a[2:100]; integer i,j; for i := 2 step 1 until 100 do a[i] := true; for i := 2 step 1 until 10 do if a[i] then for j := 2 step 1 until 1000÷i do a[i × j] := false; for i := 2 step 1 until 100 do if a[i] then print (i); end
質數素性檢測
素性檢測一般用於數學或者加密學領域。用一定的算法來確定輸入數是否是素數。不同於整數分解，素性測試一般不能得到輸入數的素數因子，只説明輸入數是否是素數。大整數的分解是一個計算難題，而素性測試是相對更為容易（其運行時間是輸入數字大小的多項式關係）。有的素性測試證明輸入數字是素數，而其他測試，比如米勒 - 拉賓（Miller–Rabin ）則是證明一個數字是合數。因此，後者可以稱為合性測試。
素性測試通常是概率測試（不能給出100%正確結果）。這些測試使用除輸入數之外，從一些樣本空間隨機出去的數；通常，隨機素性測試絕不會把素數誤判為合數，但它有可能為把一個合數誤判為素數。誤差的概率可通過多次重複試驗幾個獨立值a而減小；對於兩種常用的測試中，對任何合數n，至少一半的a檢測n的合性，所以k的重複可以減小誤差概率最多到
，可以通過增加k來使得誤差儘量小。
隨機素性測試的基本結構：
1、隨機選取一個數字a。
2、檢測某個包含a和輸入n的等式（與所使用的測試方法有關）。如果等式不成立，則n是合數，a作為n是合數的證據，測試完成。
3、從1步驟重複整個過程直到達到所設定的精確程度。
在幾次或多次測試之後，如果n沒有被判斷為合數，那麼可以説n可能是素數。
常見的檢測算法：費馬素性檢驗（Fermat primality test），米勒拉賓測試（Miller–Rabin primality test） ，Solovay–Strassen測試，盧卡斯-萊默檢驗法（Lucas–Lehmer primality test）。
質數篩素數法
篩素數法可以比枚舉法節約極大量的時間（定n為所求最大值，m為≤n的質數個數，那麼枚舉需要O（n^2）的時間複雜度，而篩素數法為O（m*n）,顯然m<<n，所以時間效率有很大提升。）。如1000000的數據範圍，用篩素數法可在2s內解決。
思路：建立一個bool型數組M，若已知一個數M[k]是質數，那麼其i（i為正整數）倍M[k*i]必然為合數，可將其去除。
//c++代碼 all rights reserve.
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long size=1000000;//修改此值以改變要求到的最大值
bool zhishu[size+5]={false};
int main（）{
freopen（"zhishu.out","w",stdout）;//輸出答案至“篩質數（shaizhishu）.exe”所在文件夾內
zhishu[2]=true;
for（long long i=3;i<=size;i+=2）zhishu[i]=true;//所有奇數標為true，偶數為false
for（long long i=3;i<=size;i++）{
if（zhishu[i]）{//如果i是質數
int cnt=2;
while（cnt*i<=size）{//把i的倍數標為false（因為它們是合數）
zhishu[cnt*i]=false;
cnt++;
}
}
}
int cnt=1;
for（int i=2;i<=size;i++）{//全部遍歷一遍
if（zhishu[i]）{//如果仍然標記為true（是質數）則輸出
cout<<cnt<<' '<<i<<endl;
cnt++;
}
}
return 0;
}
/*
樣例輸出結果，第一個數是個數，第二個是第幾個質數
1 2
2 3
3 5
4 7
5 11
6 13
7 17
8 19
9 23
10 29
11 31
12 37
13 41
14 43
15 47
16 53
17 59
18 61
19 67
20 71
21 73
22 79
23 83
24 89
25 97
*/
篩選法的Java實現，如下：
/**
* @title SOE
* @desc 簡單的埃氏篩選法計算素數
* @author he11o
* @date 2016年5月3日
* @version 1.0
*/
public class SOE {
public static int calPrime（int n）{
if（n<=1）{
return 0;
}
byte[] origin = new byte[n+1];
int count = 0;
for（int i=2;i<n+1;i++）{
if（origin[i] == 0）{
count++;
int k = 2;
while（i*k<=n）{
origin[i*k] = 1;
k++;
}
}else{
continue;
}
}
return count;
}
}
採用簡單的埃氏篩選法和簡單的開方判斷素數法計算1000000以內素數的個數的效率比較：
StopWatch '計算1000000以內素數的個數': running time （millis） = 268
-----------------------------------------
ms % Task name
-----------------------------------------
00024 009% 簡單的埃氏篩選法；
00244 091% 簡單的開方判斷素數法。
質數猜想
哥德巴赫猜想：是否每個大於2的偶數都可寫成兩個素數之和？
孿生素數猜想：孿生素數就是差為2的素數對，例如11和13。是否存在無窮多的孿生素數？
斐波那契數列內是否存在無窮多的素數？
是否有無窮多個的梅森素數？
在n2與（n+1）2之間是否每隔n就有一個素數？
是否存在無窮個形式如X2+1素數？
質數哥德巴赫猜想
在1742年給歐拉的信中哥德巴赫提出了以下猜想：任一大於2的整數都可寫成兩個質數之和。因現今數學界已經不使用“1也是素數”這個約定，原初猜想的現代陳述為：任一大於5的整數都可寫成三個質數之和。歐拉在回信中也提出另一等價版本，即任一大於2的偶數想陳述為歐拉的版本。
把命題"任一充分大的偶數都可以表示成為一個素因子個數不超過a個的數與另一個素因子不超過b個的數之和"記作"a+b"。1966年陳景潤證明了"1+2"成立，即"任一充分大的偶數都可以表示成二個素數的和，或是一個素數和一個半素數的和"。
今日常見的猜想陳述為歐拉的版本，即任一大於2的偶數都可寫成兩個素數之和，亦稱為“強哥德巴赫猜想”或“關於偶數的哥德巴赫猜想”。
若關於偶數的哥德巴赫猜想是對的，則關於奇數的哥德巴赫猜想也會是對的。1937年時前蘇聯數學家維諾格拉多夫已經證明充分大的奇質數都能寫成三個質數的和，也稱為“哥德巴赫-維諾格拉朵夫定理”或“三素數定理”。2013年，秘魯數學家哈拉爾德·赫爾弗戈特在巴黎高等師範學院宣稱：證明了一個“弱哥德巴赫猜想”，即“任何一個大於7的奇數都能被表示成3個奇素數之和”。
質數黎曼猜想
素數在自然數中的分佈並沒有簡單的規律。黎曼發現素數出現的頻率與黎曼ζ函數緊密相關。黎曼猜想提出：黎曼ζ函數ζ（s）非平凡零點（在此情況下是指s不為-2、-4、-6等點的值）的實數部份是1/2。即所有非平凡零點都應該位於直線1/2 + ti（“臨界線”（critical line））上。t為一實數，而i為虛數的基本單位。無人給出一個令人信服的關於黎曼猜想的合理證明。
在黎曼猜想的研究中，數學家們把複平面上 Re（s）=1/2 的直線稱為 critical line。 運用這一術語，黎曼猜想也可以表述為：黎曼ζ 函數的所有非平凡零點都位於 critical line 上。
黎曼猜想是黎曼在 1859 年提出的。在證明素數定理的過程中，黎曼提出了一個論斷：Zeta函數的零點都在直線Res（s） = 1/2上。他在作了一番努力而未能證明後便放棄了，因為這對他證明素數定理影響不大。但這一問題仍然未能解決，甚至於比此假設簡單的猜想也未能獲證。而函數論和解析數論中的很多問題都依賴於黎曼假設。在代數數論中的廣義黎曼假設更是影響深遠。若能證明黎曼假設，則可帶動許多問題的解決。
質數孿生質數
1849年，波林那克提出孿生質數猜想（the conjecture of twin primes），即猜測存在無窮多對孿生質數。猜想中的“孿生質數”是指一對質數，它們之間相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孿生質數。
英國數學家戈弗雷·哈代和約翰·李特爾伍德曾提出一個“強孿生素數猜想”。這一猜想不僅提出孿生素數有無窮多對，而且還給出其漸近分佈形式。2013年5月14日，《自然》（Nature）雜誌在線報道張益唐證明了“存在無窮多個之差小於7000萬的素數對”，這一研究隨即被認為在孿生素數猜想這一終極數論問題上取得了重大突破，甚至有人認為其對學界的影響將超過陳景潤的“1+2”證明。
[3]
質數梅森質數
17世紀還有位法國數學家叫梅森，他曾經做過一個猜想：當2p-1 中的p是質數時，2p-1是質數。他驗算出：當p=2、3、5、7、17、19時，所得代數式的值都是質數，後來，歐拉證明p=31時，2p-1是質數。 p=2，3，5，7時，2p-1都是素數，但p=11時，所得2,047=23×89卻不是素數。
梅森去世250年後，美國數學家科爾證明，267-1=193,707,721×761,838,257,287，是一個合數。這是第九個梅森數。20世紀，人們先後證明：第10個梅森數是質數，第11個梅森數是合數。
由於這種質數珍奇而迷人，它被人們稱為“數學珍寶”。值得一提的是，中國數學家和語言學家周海中根據已知的梅森質數及其排列，巧妙地運用聯繫觀察法和不完全歸納法，於1992年正式提出了梅森素質分佈的猜想，這一重要猜想被國際上稱為“周氏猜測”。
- 參考資料
-
- 1. Green, B. and Tao, T.．The primes contain arbitrarily long and arithmetic progression：Annals of Mathematics ，2005-09-12
- 2. 陳景潤．大偶數表為一個素數及一個不超過二個素數的乘積之和：中國科學A輯，1973, (2)：111–128
- 3. 華人破譯孿生素數猜想 影響或超陳景潤1+2證明 ．人民網
