Sicily-1009 梅森素数

一．梅森素数

素数有无穷多个，却只有极少量的素数能表示成2p－1（p为素数）的形式。在不大于257的素数中，当p=2、3、5、7、13、17、19、31、67、127、257时，2p－1是素数，其它都是合数。前面的7个数（即2、3、5、7、13、17、19）已被前人所证实，而后面的4个数（即31、67、127、257）则是梅森自己的推断。2300多年来，人类仅发现48个梅森素数。

指数为11, 23, 29, 37, 41, 43, 47, 53, 59的时候是合数。

二．过程

1. 给出2-64里面能符合梅森素数且是合数的指数数组。
2. 一个一个数进行判断，用判断素数的方法，如果是合数的话就打印出它的素数乘法因子。

三．源码（超时）

超时代码：

 //
 //  main.cpp
 //  sicily-1009
 //
 //  Created by ashley on 14-10-10.
 //  Copyright (c) 2014年 ashley. All rights reserved.
 // #include <iostream>
 #include <cmath>
 using namespace std;
 int primes[] = {, , , , , , , , , , , , , , , , , };
 int main(int argc, const char * argv[])
 {
     int k;
     cin >> k;
     for (int i = ; primes[i] <= k; i++) {
         long long number = (long long)pow(2.0, primes[i]) - ;
         long long composite = number;
         bool firsttime = true;
         bool iscomposite = false;
         for (long long j = ; j * j <= number; j++) {
             if (number % j == ) {
                 number = number / j;
                 iscomposite = true;
                 if (firsttime) {
                     firsttime = false;
                     cout << j << " ";
                 } else {
                     cout << "* " << j << " ";
                 }
             }
         }
         if (iscomposite) {
             cout << "* " << number << " ";
             cout << " = " << composite << " = ( 2 ^ " << primes[i] << " ) - 1" << endl;
         }
     }
     return ;
 }

通过代码：

 //
 //  main.cpp
 //  sicily-1009
 //
 //  Created by ashley on 14-10-10.
 //  Copyright (c) 2014年 ashley. All rights reserved.
 // #include <iostream>
 #include <cmath>
 using namespace std;
 int primes[] = {, , , , , , , , , , , , , , , , };
 int main(int argc, const char * argv[])
 {
     int k;
     cin >> k;
     for (int i = ; primes[i] <= k; i++) {
         long long number = (long long)pow(2.0, primes[i]) - ;
         long long composite = number;
         bool firsttime = true;
         bool iscomposite = false;
         long long factor = ;
         for (long long j = factor; j * j <= number; j++) {
             if (number % j == ) {
                 number = number / j;
                 iscomposite = true;
                 if (firsttime) {
                     firsttime = false;
                     cout << j << " ";
                 } else {
                     cout << "* " << j << " ";
                 }
             } //else {
 //                factor++;
 //            }
         }
         if (iscomposite) {
             cout << "* " << number << " ";
             cout << "= " << composite << " = ( 2 ^ " << primes[i] << " ) - 1" << endl;
         }
     }
     return ;
 }

四．补充：产生素数的算法：

五．指数函数：pow double pow (double base, double exponent);

六．不知道为什么要去掉61，提前算好的吗？这样有意思吗？直接switch不就好了？