时间:2021-05-20
问题描述
梅森数(Mersenne Prime)指的是形如2n-1的正整数,其中指数n是素数,即为Mn。如果一个梅森数是素数,则称其为梅森素数。例如22-1=3、23-1=7都是梅森素数。
当n=2,3,5,7时,Mn 都是素数,但n=11时,Mn=M11=211-1=2047=23X89,显然不是梅森素数。
1722年,瑞士数学大师欧拉证明了231-1=2147483647是一个素数,它共有10位数,成为当时世界上已知的最大素数。
迄今为止,人类仅发现了47个梅森素数。梅森素数历来都是数论研究中的一项重要内容,也是当今科学探索中的热点和难点问题。
试求出指数n<20的所有梅森素数。
问题分析
要编程求解的问题是找出指数n<20的所有梅森素数。根据梅森素数的定义,我们可以先求出n<20的所有梅森数,再逐一判断这些数是否为素数。如果是素数,则表示该数为梅森素数,打印输出即可;否则不是梅森素数。
算法设计
要求出n<20的所有梅森数,因此在本题的算法设计中需要釆用循环结构。
设变量mp存储梅森数,整数i表示指数,其取值从2〜19,i每变化一次,都相应的计算出一个梅森数,存放在mp中。对每次计算得到的当前mp值,都调用函数prime()进行判断。
在判断mp是否为素数时,可以定义一个函数prime(),每次都将mp的当前值作为实参传递给函数prime(),并判断是否为素数。如果n为素数,则prime()函数返回值为1,否则prime()函数返回值为0。
若prime()函数返回值为1,则当前mp为梅森素数,应该将其输出;若prime()函数返回值为0,则当前mp不是梅森素数。
程序流程图:
下面是完整的代码:
#include <math.h>#include <stdio.h>int prime(int n){int i;long k;k=sqrt(n)+1;for(i=2; i<=k; i++)if(n%i == 0)return 0;return 1;}int main(){int mp, n=0, i;printf("Mersenne Prime:\n");for(i=2; i<=20; i++){mp=pow(2,i)-1;if( prime(mp) ){n++;printf("M(%d)=%d", i, mp);printf("\n");}}printf("the number of Mersenne Prime less than 20 is:%d\n", n);return 0;}运行结果:
Mersenne Prime:
M(2)=3
M(3)=7
M(5)=31
M(7)=127
M(13)=8191
M(17)=131071
M(19)=524287
the number of Mersenne Prime less than 20 is:7
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对的支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了C语言实现求定积分的方法。分享给大家供大家参考。具体实现方法如下:复制代码代码如下:#include#include#defineACC1000f
本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下//哈夫曼树C语言实现#include#includetypedefstructHuf
本文实例为大家分享了C语言实现24点游戏的具体代码,供大家参考,具体内容如下参考文章:C语言实现经典24点算法将算法实现改成C语言,并可在linux服务器上运行
C语言实现矩阵翻转上下翻转与左右翻转实例代码:#includevoidmatrix(intm,intn,intt){intarr[m][n];inti,j,k;
本文实例为大家分享了C语言实现航班管理系统的具体代码,供大家参考,具体内容如下#include#include#