首页 > 代码库 > Sicily-1009 梅森素数
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的时候是合数。
二．过程
- 给出2-64里面能符合梅森素数且是合数的指数数组。
- 一个一个数进行判断，用判断素数的方法，如果是合数的话就打印出它的素数乘法因子。
三．源码（超时）
超时代码：
1 // 2 // main.cpp 3 // sicily-1009 4 // 5 // Created by ashley on 14-10-10. 6 // Copyright (c) 2014年 ashley. All rights reserved. 7 // 8 9 #include <iostream>10 #include <cmath>11 using namespace std;12 int primes[18] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};13 int main(int argc, const char * argv[])14 {15 int k;16 cin >> k;17 for (int i = 0; primes[i] <= k; i++) {18 long long number = (long long)pow(2.0, primes[i]) - 1;19 long long composite = number;20 bool firsttime = true;21 bool iscomposite = false;22 for (long long j = 2; j * j <= number; j++) {23 if (number % j == 0) {24 number = number / j;25 iscomposite = true;26 if (firsttime) {27 firsttime = false;28 cout << j << " ";29 } else {30 cout << "* " << j << " ";31 }32 }33 }34 if (iscomposite) {35 cout << "* " << number << " ";36 cout << " = " << composite << " = ( 2 ^ " << primes[i] << " ) - 1" << endl;37 }38 }39 return 0;40 }
通过代码：
1 // 2 // main.cpp 3 // sicily-1009 4 // 5 // Created by ashley on 14-10-10. 6 // Copyright (c) 2014年 ashley. All rights reserved. 7 // 8 9 #include <iostream>10 #include <cmath>11 using namespace std;12 int primes[18] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};13 int main(int argc, const char * argv[])14 {15 int k;16 cin >> k;17 for (int i = 0; primes[i] <= k; i++) {18 long long number = (long long)pow(2.0, primes[i]) - 1;19 long long composite = number;20 bool firsttime = true;21 bool iscomposite = false;22 long long factor = 2;23 for (long long j = factor; j * j <= number; j++) {24 if (number % j == 0) {25 number = number / j;26 iscomposite = true;27 if (firsttime) {28 firsttime = false;29 cout << j << " ";30 } else {31 cout << "* " << j << " ";32 }33 } //else {34 // factor++;35 // }36 }37 if (iscomposite) {38 cout << "* " << number << " ";39 cout << "= " << composite << " = ( 2 ^ " << primes[i] << " ) - 1" << endl;40 }41 }42 return 0;43 }
四．补充：产生素数的算法：
五．指数函数：pow double pow (double base, double exponent);
六．不知道为什么要去掉61，提前算好的吗？这样有意思吗？直接switch不就好了？
Sicily-1009 梅森素数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。