麥森數

麥森數是數學上的專業術語，是形如2^P-1的素數。

名詞解釋

形如2^P-1的素數稱為麥森數，這時P一定也是個素數。但反過來不一定，即如果P是個素數，2^P-1不一定也是素數。到1998年底，人們已找到了37個麥森數。最大的一個是P=3021377，它有909526位。麥森數有許多重要套用，它與完全數密切相關。

實現

Pascal語言

type arr=array[1..500]of longint;
var n,p,i,j:longint;
ans,num:arr;
function mul(a,b:arr):arr;
var i,j:longint;
c:arr;
begin
for i:=1 to 500 do c[i]:=0;
for i:=1 to 500 do
for j:=1 to 500-i+1 do
c[i+j-1]:=c[i+j-1]+a[i]*b[j];
for i:=1 to 499 do begin
c[i+1]:=c[i+1]+c[i] div 10;
c[i]:=c[i] mod 10;
end;
c[500]:=c[500] mod 10;
mul:=c;
end;
begin
read(p);
n:=p;
ans[1]:=1; num[1]:=2;
while p>0 do begin
if p mod 2=1 then ans:=mul(ans,num);
p:=p div 2;
num:=mul(num,num);
end;
writeln(trunc(n*ln(2)/ln(10))+1);
dec(ans[1]); p:=1;
for i:=500 downto 1 do
begin
if p=50 then begin writeln(ans[i]);p:=1;end
else begin write(ans[i]); inc(p); end;
end;
end.

C++語言

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int a[502],b[502];
void mul(int *x,int *y){
int c[501];
memset(c,0,sizeof(c));
for(int i=1;i<=500;++i)
for(int j=1;j<=500-i+1;++j)
c&#91;i+j-1&#93;+=x&#91;i&#93;*y&#91;j&#93;;
for(int i=1;i<=500;++i){
c&#91;i+1&#93;+=c&#91;i&#93;/10;
c&#91;i&#93;%=10;
}
memcpy(x,c,sizeof(int)*502);
}
int main()
{
int p;
cin>>p;
cout<<int(p*log10(2)+1)<<endl;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
b[1]=2; a[1]=1;
while(p){
if(p&1) mul(a,b);
p>>=1;
mul(b,b);
}
a[1]--;
for(int i=1;i<=500;++i)
if(a&#91;i&#93;<0){
a&#91;i+1&#93;--;
a&#91;i&#93;+=10;
}
for(int i=500;i>=1;--i) cout<<a&#91;i&#93;;
cout<<endl;
return 0;
}