麦森数-大数乘法

麦森数--大数乘法

麦森数：

形如2p-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2p-1不一定也是素数。

 1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #define N 126 6 using namespace std; 7 int ans[N],anspow[N]; 8 void mult(int ans[],int anspow[]) 9 {10   int i,j;11   int c[N];12   memset(c,0,sizeof(c));13         for(i=0;i<N;i++)  14         {  15             for(j=0;j<N;j++)                  16             {  17                 if(i+j<N)//超出500位的部分不计算18                 {19                   c[i+j]+=ans[j]*anspow[i]; 20                 }                              21             }  22            for(j=0;j<N-1;j++)  23            {  24                 if(c[j]>=10000) 25                 {  26                     c[j+1]+=c[j]/10000;//压4位  27                      c[j]%=10000;              28                 }                    29            }  30         }  31         memcpy(ans,c,N*sizeof(int));  //复制函数32 }33 int main()34 {35   int P,i,j;36   while(cin>>P)37   {38     memset(ans,0,sizeof(ans));39     memset(anspow,0,sizeof(anspow));40     printf("%d\n",(int)(P*log10(2)+1));41     ans[0]=1;42     anspow[0]=2;43 /************关键部分计算2^P*******44  2^p=（2^1）*（2^2）*（2^3）*（2^4）*（2^5）………………45  简单说下：P=5 -----101（二进制）46     p & 1 =1（最右边一位） -->>>ans=2 anspow=247     p>>1=110  anspow=2^248     p & 1 =0  此时表明2^3不存在 ans=2 anspow=2^449     p>>1=1       50     p & 1 =1  ------>>>>> ans=2^5 51     p>>1=0   ------结束    52 ************************************/53     while(P)54     {55         if( P & 1)56             mult(ans,anspow);57         P>>=1;58             mult(anspow,anspow);59     }60     ans[0]--;//2^P的个位为2，4，6，8，故可以-161 /****************输出格式的控制************************/62     for(i=124;i>=0;i--)63     {64         if(i%25==12)  65         {66            printf("%02d\n%02d",ans[i]/100,ans[i]%100);  67         }68         else  69         {  70            printf("%04d",ans[i]);71            if(i%25==0) printf("\n");72         }     73     }74 /***************************************************/75   }76 return 0;77 }

关于求解 2^p 部分的解释：

 将p转化为二进制01码， 即形如（a*2^1+b*2^2+c*2^3....） (a,b,c =0,1)

以p=5 举例： p=101;  即 阶乘1,2,3的系数分别为1,0,1；

将p与1进行&运算 ，当结果为1时，p最右端的阶乘级系数为1；

即  101&1=1  ->   a=1;

101>>1 = 10, 10&1=0;  b->0;

10>>1=1; 1&1=1 ; c->=1;

所以2^p= 2^1 * 2^ 2^2;