質數

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 #include 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#include#includeusing 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

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;varbegin 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 += 6) { if (n % i == 0 || n % (i + 2) == 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 TrueEnd Function

ALGOL代碼

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

素性檢測

上下素性判決定法

首先，本文英文字母都表示整數，上半部B》3N》W，下半部B》W》3N。大於3的素數只有6N-1和6N+1兩種形式，我們只需判定這兩種數是素數還是合數即可。

命題1對於B=36N+1型數而言。

若不定方程有整數解，

則6(3N-W)+1是小因子數；6(3N+W)+1是大因子數。

若不定方程有整數解，

則6(3N-W)-1是小因子數；6(3N+W)-1是大因子數。

兩式都無解，是素數。

命題2對於B=36N+7形數而言。

若不定方程有整數解，

則6(3N-W)+1是小因子數，6(3N+W+1)+1是大因子數。

若不定方程有整數解，

則6(3N+2-W)-1是小因子數，6(3N+W+3)-1是大因子數。

兩式都無解，是素數。

命題3對於B=36N+13形數而言。

若不定方程有整數解，

則6(3N+1-W)+1是小因子數，6(3N+1+W)+1是大因子數。

若不定方程有整數解，

則6(3N+2-W)-1是小因子數，6(3N+2+W)-1是大因子數。

兩式都無解，是素數。

命題4對於B=36N+19形數而言。

若不定方程有整數解，

則6(3N+1-W)+1是小因子數；6(3N+2+W)+1是大因子數。

若不定方程有整數解，

則6(3N+1-W)-1是小因子數；6(3N+2+W)-1是大因子數。

兩式都無解，是素數。

命題5對於B=36N+25形數而言。

若不定方程有整數解，

則6(3N+2-W)+1是小因子數，6(3N+2+W)+1是大因子數。

若不定方程有整數解，

則6(3N+1-W)-1是小因子數，6(3N+1+W)-1是大因子數。

兩式都無解，是素數。

命題6對於B=36N+31形數而言。

若不定方程有整數解，

則6(3N+2-W)+1是小因子數，6(3N+3+W)+1是大因子數。

若不定方程有整數解，

則6(3N-W)-1是小因子數，6(3N+1+W)-1是大因子數。

兩式都無解，是素數。

命題7對於B=36N-1形數而言。

若不定方程有整數解，應該是（B+1）

則6(3N-W)+1是小因子數；6(3N+W)-1是大因子數。

若不定方程有整數解，應該是（B+1）

則6(W-3N)-1是小因子數；6(W+3N)+1是大因子數。

兩式都無解，是素數。

命題8對於B=36N+5形數而言。

若不定方程有整數解，

則6(W-3N)+1是小因子數，6(W+3N+1)-1是大因子數。

若不定方程有整數解，

則6(W-3N-2)-1是小因子數，6(W+3N+3)+1是大因子數。

兩式都無解，是素數。

命題9對於B=36N+11形數而言。

若不定方程有整數解，

則6(W-3N-1)+1是小因子數，6(W+3N+1)-1是大因子數。

若不定方程有整數解，

則6(W-3N-2)-1是小因子數，6(W+3N+2)+1是大因子數。

兩式都無解，是素數。

命題10對於B=36N+17形數而言。

若不定方程有整數解，

則6(W-3N-1)+1是小因子數；6(W+3N+2)-1是大因子數。

若不定方程有整數解，

則6(W-3N-1)-1是小因子數；6(W+3N+2)+1是大因子數。

兩式都無解，是素數。

命題11對於B=36N+23形數而言。

若不定方程有整數解，

則6(W-3N-2)+1是小因子數，6(W+3N+2)+1是大因子數。

若不定方程有整數解，

則6(W-3N-1)-1是小因子數，6(W+3N+1)+1是大因子數。

兩式都無解，是素數。

命題12對於B=36N+29形數而言。

若不定方程有整數解，

則6(W-3N-2)+1是小因子數，6(W+3N+3)-1是大因子數。

若不定方程有整數解，

則6(W-3N)-1是小因子數，6(W+3N+1)+1是大因子數。

兩式都無解，是素數。

素性檢測一般用於數學或者加密學領域。用一定的演演算法來確定輸入數是否是素數。不同於整數分解，素性測試一般不能得到輸入數的素數因子，只說明輸入數是否是素數。大整數的分解是一個計算難題，而素性測試是相對更為容易（其運行時間是輸入數字大小的多項式關係）。有的素性測試證明輸入數字是素數，而其他測試，比如米勒-拉賓（Miller–Rabin）則是證明一個數字是合數。因此，後者可以稱為合性測試。

素性測試通常是概率測試（不能給出100%正確結果）。這些測試使用除輸入數之外，從一些樣本空間隨機出去的數；通常，隨機素性測試絕不會把素數誤判為合數，但它有可能為把一個合數誤判為素數。誤差的概率可通過多次重複試驗幾個獨立值a而減小；對於兩種常用的測試中，對任何合數n，至少一半的a檢測n的合性，所以k的重複可以減小誤差概率最多到，可以通過增加k來使得誤差盡量小。

隨機素性測試的基本結構：

1.隨機選取一個數字a。

2.檢測某個包含a和輸入n的等式（與所使用的測試方法有關）。如果等式不成立，則n是合數，a作為n是合數的證據，測試完成。

3.從1步驟重複整個過程直到達到所設定的精確程度。

在幾次或多次測試之後，如果n沒有被判斷為合數，那麼我們可以說n可能是素數。

常見的檢測演演算法：費馬素性檢驗（Fermatprimalitytest），米勒拉賓測試（Miller–Rabinprimalitytest），Solovay–Strassen測試，盧卡斯-萊默檢驗法（Lucas–Lehmerprimalitytest）。

篩素數法

篩素數法可以比枚舉法節約極大量的時間（定n為所求最大值，m為≤n的質數個數，那麼枚舉需要O(n^2)的時間複雜度，而篩素數法為O(m*n),顯然m<

思路：建立一個bool型數組M，若已知一個數M[k]是質數，那麼其i（i為正整數）倍M[k*i]必然為合數，可將其去除。

//c++代碼 all rights reserve.#include#include#includeusing 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<

篩選法的Java實現，如下：

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

採用簡單的埃氏篩選法和簡單的開方判斷素數法計算1000000以內素數的個數的效率比較：

StopWatch'計算1000000以內素數的個數':runningtime(millis)=268

-----------------------------------------

ms%Taskname

-----------------------------------------

00024009%簡單的埃氏篩選法

00244091%簡單的開方判斷素數法

猜想

---

哥德巴赫猜想：是否每個大於2的偶數都可寫成兩個素數之和？

孿生素數猜想：孿生素數就是差為2的素數對，例如11和13。是否存在無窮多的孿生素數？

斐波那契數列內是否存在無窮多的素數？

是否有無窮多個的梅森素數？

在n與(n+1)之間是否每隔n就有一個素數？

是否存在無窮個形式如X+1素數？

黎曼猜想

孿生素數無限多的證明

---

陰性合數定理和陰性素數定理

大於3的素數只分佈在6n-1和6n+1兩數列中。（n非0自然數，下同）

6n-1數列中的合數叫陰性合數，其中的素數叫陰性素數（q）。

6[6NM+（M-N）]-1=（6N+1）（6M-1）（NM兩個非0自然數，N=〈M，下同）

6乘以陰性上等數減去1等於陰性上合數。

6[6NM-（M-N）]-1=（6N-1）（6M+1）

6乘以陰性下等數減去1等於陰性下合數。

在6n-1數列中只有這兩種合數，餘下就是陰性素數了，所以就有陰性素數定理

x=/=6NM+-（M-N）

陰性不等數不等於陰性上下兩式。

6x-1=q

6乘以陰性不等數減去1等於陰性素數。

陽性合數定理和陽性素數定理

6n+1數列中的合數叫陽性合數，其中的素數叫陽性素數（P）。

6[6NM+（N+M）]+1=（6N+1）（6M+1）

6乘以陽性上等數加上1等於陽性上合數。

6[6NM-（N+M）]+1=（6N-1）（6M-1）

6乘以陽性下等數加上1等於陽性下合數。

在6n+1數列中只有這兩種合數，餘下就是陽性素數了，所以就有陽性素數定理

X=/=6NM+-（N+M）

陽性不等數不等於陽性上下兩式。

6X+1=P

6乘以陽性不等數加上1等於陽性素數。

與孿生素數相對應的完全不等數

（X）=/=6NM+-（M+-N）

完全不等數,它既不等於陰性上下兩式；也不等於陽性上下兩式。

6（X）+1=P

6乘以完全不等數加上1等於陽性素數；

6（X）-1=q

6乘以完全不等數減去1等於陰性素數。

一個完全不等數所產生的陰性素數q和陽性素數P就是一對孿生素數.

並且完全不等數與孿生素數是一一對應的.

四。陰陽四種等數在自然數列中的分佈概況

6NM+（M-N）=陰性上等數6NM-（M-N）=陰性下等數

6NM+（N+M）=陽性上等數6NM-（N+M）=陽性下等數

為了搞清它們在自然數中分佈情況，把四式中的N叫級別因子數，M叫無限因子數。

四種等數的每一個級別的最小等數都在6NN+-（N+N）範圍。

每一級別的上等數相鄰兩等數距離是6n+1，在自然數列中比例是1/（6n+1），陰陽兩種上等數每個級別的比例合計是2/（6n+1），（但實際是略少於這個比例，因每一級別的底部都沒有這個級別的等數。）

每一級別的下等數相鄰等數的距離是6n-1，在自然數列中的比例是1/（6n-1），陰陽兩種下等數的每個級別的合計比例是2/（6n-1），（但實際是略少於這個比例，因每一級別的底部都沒有這個級別的等數。）

在相對應的級別標準單位的連續自然數篩掉一個級別的四種等數后，剩下非該級別的自然數的比例是[（6N-1）（6N-3）]/[（6N+1）（6N-1）].並且是精準的。

四種等數大小數列的互相滲透

自然數列中在陰性方面有陰性上等數數列和陰性的下等數數列；自然數數列在陽性方面陽性上等數數列和陽性下等數數列。它們的級別有無限多，每一個級別的數列的等數也是無限多的。同一種等數級別不同的數列都是互相滲透而產生重疊，並以兩級別的等數距離的乘積而嚴格地重疊的。篩掉N及以下級別的等數用連乘式正好可以表示它們的滲透重疊關係。

四種等數數列之間都有互相滲透而重疊，只有同一級別陰陽上上數列.下下數列沒有滲透。

如第一級別的陽性下等數，從4開始每隔5個自然數就是一個第一級別的陽性下等數，它的比例是1/5，只要大於3的任何連續5個自然數，第一級別陽性下等數的比例是1/5，並且永遠不變。第一級別的陰性下等數從6開始每隔5個個自然數就是一個陰性下等數，它的比例是1/5,只要大於5的連續5個自然數，第一級別陰性下等數的1/5的比例也是永恆的。這樣第一級別的陰陽兩種下等數的比例是2/5，在任何大於5的5個連續自然數這個比例也是永恆的。第一級別的陰陽兩種上等數2/7,只要是連續7的自然數這個比例也是永恆的。由於上下兩等數的互相重疊，它們的比例是20/35,為什麼不是4/7,因為只有在大於7的連續35個自然數這個比例是不變的，如果連續7個自然數，它的比例有時是2/7,有時是3/7，有時是4/7.

其它級別也是一樣的。但如果這個級別的等數間隔距離是合數的，這個級別的等數都與前面級別的等數重疊的，所以這些級別就不用計算了。

這樣就立出以下的計算公式：

（6NN+6N）*3/5*5/7*9/11*11/13*......*（p-2）/p

（6NN+6N）是一個自然數的大體表達式，P《=NN以內最大的素數。

對應數段與同步區間

1、對應數段和精準的比例

計算一個級別的四種等數，只有在同一級別的對應數段為單位才是精準的比例，不然就有誤差。

一個N級別的標準單位是（6N+1）（6N-1）；在計算N級別及以下的四種等數，它們的對應數段是N級別及以下的所有有性素數（不包括2和3的素數）的乘積。

對應數段的增大速度非常快。

對應數段的對應位置一定要在大於最大級別的最小陰性等數。

在這位置以上任何連續的對應數段為單位的自然數中，它們的自己的等數是一定的，比例是精準的（不包括大於它的級別等數）。

2、與素數分佈基本同步的SN區間

把自然數劃分成12，24，36……以12為遞增的一個個區間，這樣的區間叫SN區間。即:

12（1+2+3+……+N）-12（1+2+3+......+（N-1）=（6N^2+6N）-[6（N-1）^2+6（N-1）]=12N

SN區間與四種等數數列是同步的。

在這樣的區間內包括N級別及以下的所有四種等數數列的等數，並沒有比N級別大的數列等數，與四種等數的級別是完全同步的，所以與素數的分佈也是同步的。

大於S8區間內都有8個以上的完全不等數

在每一個SN區間只有存在1至N級別的四種數列等數，每一級別等數的比例是可以確定，由於上下級別的滲透。就可以拿以下式來計算S8區間的完全不等數的至少個數。

12*8*11/35*95/143*251/323*479/575*779/899*1151/1295*1593/1763*2111/2303=8.2768

（由於計算的區間不是對應的標準單位，肯定會有誤差，為保險起見，把各級別中合數也給算上，一個級別中上下兩種等數的重疊則沒有算。）

其他每一個SN區間可用這種方法計算.

隨著區間的增大完全不等數計算的數量也會越來越多.以後都會超過8個.

誤差分析

在計算任何區間的等數，由於標準的比例與計算的區間都不能整除，所以存在誤差是一定，由於誤差掩蓋了等數的精準比例。

由於各個區間與相對應的標準單位不能同步，一個級別及以下的所有有性素數的乘積為這個級別的對應的標準單位，一個標準單位比對應的級別區間大得很多，如第一和第二兩個級別的標準單位就有5005，第二個N區間只有24，在5005的連續自然數中就有許多比第二級別大得多的等數，所以計算出的數值大多會有誤差。只有用標準的單位計算相對應的所有級別的等數才不會有誤差，由於標準單位的增速比等數級別快得多，所以就沒有所有等數級別的標準區間。

另外，可用最嚴格下取整的誤差分析方法，將SN區間捆綁成1,2,4,8,16......2^（N-1）的LN區間.在每一個大於S8的SN區間計算都大於8個完全不等數,在每一個LN區間都有2^N-1級別等數數列,每級級別有4種等數數列,每一級別一種等數篩一次誤差極限是1.每一個LN區間誤差極限是4*（2^N-1）.

8*2^（N-1）-4*（2^N-1）=4

最嚴格下取整后大於L4的區間仍然還有4個完全不等數。

總結

根據以上的論證，在大於S8區間每一個SN區間都有8個以上的完全不等數.

嚴格的下取整后，大於L4的每一個LN區間都還有多於4個的完全不等數。

LN區間是無限多的，完全不等數與孿生素數對是一一對應的，所以孿生素數也是無限多的。

這個證明期待著權威的表態。

難題

---

哥德巴赫猜想

哥德巴赫猜想證明的困難在於，任何能找到的素數，在以下式中都是不成立的。2*3*5*7*。。。。。。*PN*P=PN+（2*3*5*7*。。。。。。*P-1）*PN前面的偶數減去任何一個素數PN的差必是合數.

在1742年給歐拉的信中哥德巴赫提出了以下猜想：任一大於2的整數都可寫成兩個質數之和。因現今數學界已經不使用“1也是素數”這個約定，原初猜想的現代陳述為：任一大於5的整數都可寫成三個質數之和。歐拉在回信中也提出另一等價版本，即任一大於2的偶數想陳述為歐拉的版本。把命題"任一充分大的偶數都可以表示成為一個素因子個數不超過a個的數與另一個素因子不超過b個的數之和"記作"a+b"。1966年陳景潤證明了"1+2"成立，即"任一充分大的偶數都可以表示成二個素數的和，或是一個素數和一個半素數的和"。今日常見的猜想陳述為歐拉的版本，即任一大於2的偶數都可寫成兩個素數之和，亦稱為“強哥德巴赫猜想”或“關於偶數的哥德巴赫猜想”。

從關於偶數的哥德巴赫猜想，可推出任一大於7的奇數都可寫成三個質數之和的猜想。後者稱為“弱哥德巴赫猜想”或“關於奇數的哥德巴赫猜想”。

若關於偶數的哥德巴赫猜想是對的，則關於奇數的哥德巴赫猜想也會是對的。1937年時前蘇聯數學家維諾格拉多夫已經證明充分大的奇質數都能寫成三個質數的和，也稱為“哥德巴赫-維諾格拉朵夫定理”或“三素數定理”。2013年，秘魯數學家哈拉爾德·赫爾弗戈特在巴黎高等師範學院宣稱：證明了一個“弱哥德巴赫猜想”，即“任何一個大於7的奇數都能被表示成3個奇素數之和”。

黎曼猜想

黎曼猜想是關於黎曼ζ函數ζ(s)的零點分佈的猜想，由數學家波恩哈德·黎曼（1826～1866）於1859年提出。德國數學家希爾伯特列出23個數學問題。其中第8問題中便有黎曼假設。素數在自然數中的分佈並沒有簡單的規律。黎曼發現素數出現的頻率與黎曼ζ函數緊密相關。黎曼猜想提出：黎曼ζ函數ζ(s)非平凡零點（在此情況下是指s不為-2、-4、-6等點的值）的實數部份是1/2。即所有非平凡零點都應該位於直線1/2+ti（“臨界線”（criticalline））上。t為一實數，而i為虛數的基本單位。無人給出一個令人信服的關於黎曼猜想的合理證明。

在黎曼猜想的研究中，數學家們把複平面上Re(s)=1/2的直線稱為criticalline。運用這一術語，黎曼猜想也可以表述為：黎曼ζ函數的所有非平凡零點都位於criticalline上。

黎曼猜想是黎曼在1859年提出的。在證明素數定理的過程中，黎曼提出了一個論斷：Zeta函數的零點都在直線Res(s)=1/2上。他在作了一番努力而未能證明后便放棄了，因為這對他證明素數定理影響不大。但這一問題仍然未能解決，甚至於比此假設簡單的猜想也未能獲證。而函數論和解析數論中的很多問題都依賴於黎曼假設。在代數數論中的廣義黎曼假設更是影響深遠。若能證明黎曼假設，則可帶動許多問題的解決。

孿生質數

證明36N（N+1）+-1形孿生素數無限多

36N（N+1）+-1形的孿生素數叫雁盪山孿生素數。如這種數對不是孿生素數的，它必有一邊或一對被小於它素數整除。

在這種數對中2和3不能整除它們，也就是2和3不參加篩選；用5當篩子時，N除以5餘2的產生的陰性數（6n-1）能被5整除，N除以5餘1，3，4和0都不能被5整除；不管N是什麼數所產生的陽性數（6n+1）都不能被5整除，這樣在所有的自然數中就有1/5被篩掉了。

用7當篩子時，N除以7餘2和4所產生的陽性數能被7整除，不管N是什麼數所產生的陰性數都不能被7整除。這樣就有2/7被篩掉了。

用11當篩子時，不管N是什麼數，所產生的陰性數和陽性數都不能被11整除，11是一個無效篩子，不參加篩選。

總之，所有的素數在篩選N時有4種情況，一，不參加篩選。二，單一參加篩選的，如5，（5是唯一一個單一篩選的）。三，成對單邊參加篩選的。四，成對兩邊都參加篩選的。

N是無限多的，被5篩掉了1/5,剩下還是無限多的。再被7篩掉了2/7,剩下的還是無限多的。再一個個篩下去不管篩掉的是2/P還是4/P，剩下永遠是無限多的。

雁盪山孿生素數就是無限多的。

1849年，波林那克提出孿生質數猜想（theconjectureoftwinprimes），即猜測存在無窮多對孿生質數。猜想中的“孿生質數”是指一對質數，它們之間相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孿生質數。

英國數學家戈弗雷·哈代和約翰·李特爾伍德曾提出一個“強孿生素數猜想”。這一猜想不僅提出孿生素數有無窮多對，而且還給出其漸近分佈形式。2013年5月14日，《自然》(Nature)雜誌在線報道張益唐證明了“存在無窮多個之差小於7000萬的素數對”，這一研究隨即被認為在孿生素數猜想這一終極數論問題上取得了重大突破，甚至有人認為其對學界的影響將超過陳景潤的“1+2”證明。

36N（N+1）+-1形的孿生素數，N《100000000有109128對。

梅森質數

梅森素數編選法

根據素數作為因子數在2^N-1數列中的分佈規律而編選梅森素數。

一在2^N-1平方根以內沒有奇素數的，這個指數的數就是梅森素數，後面的指數能被這個梅森素數整除的都有這個梅森素數的因子，周期重複的都編上這個因子數。

二在2^N-1數列中N是合數的，2^N-1是由前面素因子和新增的因子數組成，只要除去前面的因子數就能得到新的因子數，新的因子數也以這個指數為周期重複出現，並在後面重複的數編上這個因子數。

三指數是素數的，剩下的因子素數根據減1能被指數整除來選合，選合后並在後面的周期重複的數編上這些因子數；剩下的因子素數在2^N-1平方根以內選完后，還有梅森數空著，這個梅森數就是梅森素數，並在後面周期重複的數編上為些因子數。

根據以上的方法操作如下：

把2^n-1的指數都展開，從2開始編下去。

指數2的數值是3，3的平方根內沒有奇素數，所以它是梅森素數，凡是指數能被2整除的都有3的因子數，後面以2為周期編上因子數3；

指數3的數值是7，7的平方根內沒有奇素數，所以它也是梅森素數；凡是指數能被3整除的都有7的因子數，以3為周期編上因子數7；

指數4數值是15，4能被2整除所以有3的因子數，15除以3等於5，5是新出現的因子數，凡是指數能被4整除的，都有5的因子數，後面以4為周期編上因子數5；

指數是5數值是31，31的平方根以內只有3和5兩個奇素數，3和5已是指數2和4的因子數了，所以這個梅森數是梅森素數，凡是指數能被5整除的，都有31的因子數，後面以5為周期編上因子數31；

指數6數值是63，6比較特別，凡是指數能被6整除的都會再增一個3的因子數，它是唯一一個不會新增其他因子數的數，後面以6為周期再編上一個因子數3；

指數7數值是127，127的平方根以內只有奇素數11還沒有用上（實際以後都會用上的），11減1不能被7整除，所以127也是梅森素數，凡是指數能被7整除的都有127的因子數，後面以7為周期編上因子數127；

指數8數值是255，增加了17的因子數，凡是指數能被8整除的都有17的因子數，後面以8為周期編上因子數17；

指數9數值是511，新增73的因子數，凡是指數能被9整除的都有73的因子數，後面以9為周期編上因子數73；

指數10數值是1023，新增11的因子數，凡是指數能被10整除的都有11的因子數，後面以10為周期編上因子數11；

指數11數值是2047，2047的平方根內還有43，41，37，29，23，19，13等奇素數（只要往後多編一些，留下的數就更少了），只要將這幾個數都減去1，那一個數被11整除，只有23-1能被11整除，2047/23=89，23和89是它的因子數，兩個因子數都是新增加的，因為它是梅森合數，凡是指數能被11整除的都有23和89的因子數，後面以11為周期編上因子數23和89；

指數12數值是4095，已有的因子數3*7*5*3，新的因子數是13，凡是後面指能被12整除的，都編上因子數13。

指數13數值是8191，8191的平方根內還有83，79，73，71，67，61，59，53，47，43，41，29，19等素數，其中只有79-1能被13整除，用79試除也是不行，所以8191也梅森素數。

一直編下去，每一個指數至少都會新增一個素數的因子數，不是梅森素數和梅森合數的因子數都能編選出來，沒有選到的就是梅森合數的因子數和梅森素數。

編梅森數時，根據素數減1能被指數整除的定理，從剩下素數中選合。

2^N-1的平方根以內的素數都被因子數選完，留下就是梅森素數了。

梅森素數的近似計算公式：

3*5/3.8*7/5.8*11/9.8*13/11.8*......*P/（P-1.2）-1=M

P是梅森數的指數，M是P以下的梅森素數的個數。

以下是計算的數值與實際數的情況：

指數5，計算2.947，實際3，誤差0.053；

指數7，計算3.764，實際4，誤差0.236；

指數13，計算4.891，實際5，誤差0.109；

指數17，計算5.339，實際6，誤差0.661；

指數19，計算5.766，實際7，誤差1.234；

指數31，計算6.746，實際8，誤差1.254；

指數61，計算8.445，實際9，誤差0.555；

指數89，計算9.201，實際10，誤差0.799；

指數107，計算9.697，實際11，誤差1.303；

指數127，計算10.036，實際12，誤差1.964；

指數521，計算13.818，實際13，誤差-0.818；

指數607，計算14.259，實際14，誤差-0.259；

指數1279，計算16.306，實際15，誤差-1.306；

指數2203，計算17.573，實際16，誤差-1.573；

指數2281，計算17.941，實際17，誤差-0.941；

所有的奇素數都是准梅森數（2^N-1）的因子數，則梅森合數的因子數是只有素數中的一部份。

在2^N-1的數列中，一個素數作為素因子第一次出現在指數N的數中，這個素數作為因子數在2^N-1數列中就以N為周期出現。在這種數列中指數是偶數的都等於3乘以四倍金字塔數。

在2^N-1數列中，指數大於6的，除梅森素數外，都有新增一個或一個以上的素數為因子數，新增的因子數減1能被這個指數整除。

一個梅森合數的因子數只有唯一一次出現在一個梅森合數中。

一個是梅森素數的素數，它永遠不是梅森合數的因子數。

一個是前面的梅森合數的因子數，它永遠不會是後面的梅森合數的因子數。

所有梅森合數的數因子減1都能被這個梅森合數的指數整除，商是偶數。

一個素數在不是梅森合數的准梅森數中第一次以因子數出現，這個素數減1能被這個准梅森數的指數整除，商不一定是偶數。

梅森素數都在[4^（1-1）+4^（2-1）+4^（3-1）+......+4^（n-1）]*6+1數列中，括符里種數暫叫四倍金字塔數。

凡是一個素數是四倍金字塔數的因子數，以後就不是梅森合數的因子數。

在4^（1-1）+4^（2-1）+4^（3-1）+......+4^（n-1）數列中的數，有不等於6NM+-（N+M）的數乘以6加上1都是梅森素數。

在2^P-1平方根以下的素數都以素因子在以前准梅森數中出現了，那這個梅森數必是梅森素數。但它的逆定理是不成立的。如果還沒有出現在以前的准梅森數中的素數，它也不定是梅森合數的因子數。

17世紀還有位法國數學家叫梅森，他曾經做過一個猜想：當2-1中的p是質數時，2-1是質數。他驗算出：當p=2、3、5、7、17、19時，所得代數式的值都是質數，後來，歐拉證明p=31時，2-1是質數。p=2，3，5，7時，2-1都是素數，但p=11時，所得2,047=23×89卻不是素數。

梅森去世250年後，美國數學家科爾證明，2-1=193,707,721×761,838,257,287，是一個合數。這是第九個梅森數。20世紀，人們先後證明：第10個梅森數是質數，第11個梅森數是合數。質數排列得雜亂無章，也給人們尋找質數規律造成了困難。

迄今為止，人類僅發現49個梅森質數。美國中央密蘇里大學於2016年1月7日發現的質數，為迄今發現的最大質數，同時是一個梅森質數。由於這種質數珍奇而迷人，它被人們稱為“數學珍寶”。值得一提的是，中國數學家和語言學家周海中根據已知的梅森質數及其排列，巧妙地運用聯繫觀察法和不完全歸納法，於1992年正式提出了梅森素質分佈的猜想，這一重要猜想被國際上稱為“周氏猜測”。

（GIMPS）項目於2016年1月7日找到人類已知的最大素數2-1，該素數有22,338,618位，是第49個梅森素數。

2017年12月26日，美國田納西州日耳曼敦的GIMPS志願者喬納森·佩斯（JonathanPace）發現了第50個梅森素數277232917－1。這個超大素數有23249425位數，再次刷新了已知最大素數紀錄。新的紀錄是M82589933，由美國佛羅里達州奧卡拉的帕特里克·羅什在2018年12月7日發現。

基本信息

中文名

質數

外文名

prime number

別名

素數

例子

2、3、5、7

反義詞

合數

討論範圍

非0自然數

定義

只有1和它本身兩個因數的自然數