完全數、梅森數與梅森素數

質數有什麼

在古希臘時代人們就發現了4個完全數：6，28，496，8128，它們之間相差不大，但是直到15世紀才發現了第五個完全數33550336，和前面相差竟然如此遙遠，有沒有簡單法則尋找完全數呢？其實公元前300年歐幾里得已經得出了一條定理：若2^p-1是素數（也叫質數），則2^（p-1）*（2^p-1）是完全數。因此，對於一個新的p，只要能判斷2^p-1 是素數，就相當於找到了一個新的完全數。

梅森是17世紀歐洲科學界一位獨特的中心人物，是法蘭西學院的奠基人，被選為“100位在世界科學史上有重要地位的科學家”之一。他在歐幾里得、費爾馬等人研究的基礎上對2^p-1型的數做了大量的計算和驗證，於1644年在他的《物理數學隨感》一書中斷言：在不大於257的素數中，當p=2、3、5、7、13、17、19、31、67、127、257時，2^p-1是素數，其它都是合數。前面的7個數（即p=2、3、5、7、13、17、19）已經被前人所證實，而後面的4個數（p=31、67、127、257）則是梅森自己的推斷，由於梅森在科學界有崇高的學術地位，當時的人們對其斷言都深信不疑（後來人們發現其斷言包含若干錯漏）。

由於梅森的工作極大地激發了人們研究2^p-1型素數的熱情，使其擺脫了作為“完全數”的附庸地位，是一個轉折點和里程碑，為了紀念他，數學界就把2^p-1，其中p是素數的數稱為“梅森數”，並以Mp記之，即

Mp=2^p-1，若p是素數，則2^p-1叫做梅森數

，例如：2^2-1=3，2^3-1=7，2^5-1=31，2^7-1=127，前面4個都是素數；而2^11-1=2047=23*89是合數，2^13-1=8191，2^17-1=131071，2^19-1=52428，是素數；2^23-1=8388607=47*178481，又是合數……，

如果2^p-1也是素數，則稱其為梅森素數

。

分解2^p-1 的結果展示：

C語言分解梅森數程式如下：

//分解梅森數Mp=2^p-1，其中p為素數

#include

#include

#include

#define N 20

main （） //注：如果（2^p-1）是合數，一定能被（2*p+1）整除

{ void shuchu（int，unsigned ［N］）； //輸出函式原型宣告

int i，k，x，lbz，lb=1，lcz=1，lc=1； //迴圈變數i，k，x；被除數總位數lbz，單元數lb，除數總位數lcz，單元數lc

int p，ss，l，jw，g=0，jr=0； //指數p，試商ss，積的單元數l，進位jw，個數g，進入標誌jr

int lb1，lc1，lc2，b5，q，c3； //lb1=lb-1，lc1=lc-1，lc2=lcz*2-1，被除數前5位b5及其算術根q，除數前3位c3

unsigned b［N］={0，1}，c［N］={0，1}，s［N］={}，y［N*2］={}，xj； //被除數b，除數c，商s，餘數y，新積xj

printf（“請輸入素數p：”）；scanf（“%u”，&p）；

float t0=clock（）；

//求2^p-1：

for（i=1；i<=p；i++）

{ jw=0；

for（k=1；k<=lb；k++）

{ b［k］=b［k］*2+jw；

if（b［k］<=9999）jw=0； else{jw=1；b［k］-=10000；} //每4位為1個單元

}

if（jw>=1）{lb++；b［lb］=1；}

}

b［1］——；

printf（“2^%u-1=”，p）；

shuchu（lb，b）； //呼叫shuchu函式：輸出被分解數b的各單元（lb為單元數，b為陣列名）

printf（“ = 1”）； //開始分解：

p*=2；c［1］+=p； c3=c［1］；//求（2*p+1）

while （lcz<=lbz）

{ lc2=lcz*2；

if（lc2

{ lbz=lb*4；lb1=lb-1；

if（b［lb］>=1000） {b5=b［lb］*10+b［lb1］/1000；}

else if（b［lb］>=100） {lbz——；b5=b［lb］*100+b［lb1］/100；}

else if（b［lb］>=10） {lbz-=2；b5=b［lb］*1000+b［lb1］/10；}

else {lbz-=3；b5=b［lb］*10000+b［lb1］；}

q=sqrt（b5+1）； lc1=lc-1；

for（x=1；x<=lb；x++） {y［x］=b［x］；} //做除法：

for（i=lb；i>=lc；i——）

{ y［i］+=y［i+1］*10000；y［i+1］=0； s［i］=0；

while（y［i］>c［lc］）

{ if（y［i］>=429496） ss=y［i］/（c［lc］+1）； //2^32=42 9496 7296

else ss=（y［i］*10000+y［i-1］）/（c［lc］*10000+c［lc1］+1）；

if（ss==0） ss=1；

jw=0；s［i］+=ss；

for（k=1；k<=lc1；k++） //lc1=lc-1

{ xj=c［k］*ss+jw；

if（xj<=9999）jw=0； else{jw=xj/10000；xj%=10000；}

l=k+i-lc；

if（y［l］

y［l］-=xj；

}

xj=c［lc］*ss+jw；

y［i］-=xj；

}

}

while（y［lc］>=c［lc］）

{ for（x=lc；x>=1；x——）

{ if（y［x］>c［x］） break；

if（y［x］

}

s［lc］++；

for（x=1；x<=lc1；x++） //lc1=lc-1

{ if（y［x］

y［x］-=c［x］；

}

y［lc］-=c［lc］；

}

tc：

for（x=lc；x>=1；x——）

{ if（y［x］！=0） break；}

if（x！=0） //餘數 ！=0，求新的除數：

{ c［1］+=p； g++；

if（jr！=0）

{ if（g%51051！=0） //因51051=3*7*11*13*17

{ while（（g%3==0||c［1］%5==0||g%7==0||g%11==0||g%13==0||g%17==0）==1）

{ g++；c［1］+=p； }

}

else {g=1；c［1］+=p；}

}

else {if（（c［2］*10000+c［1］）%51051==0） {jr=1；g=1；c［1］+=p；}}

if（c［1］>=10000）

{ c［2］++；c［1］-=10000；

for（x=2；x<=lc；x++） { if（c［x］>=10000）{c［x+1］++；c［x］-=10000；} }

if（c［lc+1］>=1） lc++；

lcz=lc*4； lc1=lc-1；

if（c［lc］>=1000） {c3=c［lc］/10；}

else if（c［lc］>=100） {lcz——；c3=c［lc］；}

else if（c［lc］>=10） {lcz-=2；c3=c［lc］*10+c［lc1］/1000；}

else {lcz-=3；c3=c［lc］*100+c［lc1］/100；}

}

}

else // 餘數 =0，輸出因數：

{ printf（“ * ”）； shuchu（lc，c）； //呼叫shuchu函式：輸出因數c的各單元

if（s［lb］==0） lb——；lb1=lb-1；

for（x=lc；x<=lb1；x++）

{ if（s［x］>=10000） {s［x+1］++；s［x］-=10000；}

}

for（x=lc；x<=lb；x++） {b［x-lc1］=s［x］；} //求新的被除數：

lb-=lc1； //lc1=lc-1

}

}

else //分解完了輸出最後一個因數：

{ printf（“ * ”）； shuchu（lb，b）； //呼叫shuchu函式：輸出最後一個因數b的各單元

break；

}

}

printf（“\n用時%。3f秒”，（clock（）-t0）/1000）；

}

//輸出函式：

void shuchu（int lb，unsigned b［N］）

{ int x；

printf（“%u”，b［lb］）； lb——；

for（x=lb；x>=1；x——）

{ if（b［x］>=1000） printf（“ %u”，b［x］）；

else if（b［x］>=100） printf（“ 0%u”，b［x］）；

else if（b［x］>=10） printf（“ 00%u”，b［x］）；

else printf（“ 000%u”，b［x］）；

}

}