麦森数(转)

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

 1 /*************麦森数****************/
 2  #include<iostream>
 3  #include<cstdio>
 4  #include<cmath>
 5  #define N 100   //压5位
 6  using namespace std;
 7  int ans[N];
 8  void  mult(int t)
 9  {
10    int i,temp,last=0;
11        for ( i=N-1; i>=0; i--)
12      { 
13          temp=(ans[i]<<t)+last;   //乘2^t，加进位 
14          last=temp/100000; 
15          ans[i]=temp-last*100000;  //temp%100000 
16      } 
17  }
18  void output()
19  {
20     int i;
21     for(i=1;i<=N;i++)
22     {     printf("%05d",ans[i-1]);
23          if (i%10==0)cout<<endl;   
24     } 
25  }
26  int main()
27  {
28    int P,times;
29    while(cin>>P)
30    {
31        memset(ans,0,sizeof(ans));
32        ans[N-1]=1;
33        cout<<(int)(P*log10(2)+1)<<endl;
34  /***********************关键部分*****************
35    2^P=2^(14*times)*2^(P%14) 用移位
36    之所以取14的原因 2^14*(99999)=1.638382*10^9 在（int）
37    范围，15以后都会超int，主要体现在mult()中      
38   **********************************************/
39        times=P/14;  //只能到14 15以后压缩时会超范围
40        while(times--)
41            mult(14);
42         mult(P%14);
43         --ans[99];
44        output();
45    }
46  return 0;
47  }