内容简介:梅森数(Mersenne Prime)指的是形如2当n=2,3,5,7时,M1722年,瑞士数学大师欧拉证明了2
问题描述
梅森数(Mersenne Prime)指的是形如2 n -1的正整数,其中指数n是素数,即为M n 。如果一个梅森数是素数,则称其为梅森素数。例如2 2 -1=3、2 3 -1=7都是梅森素数。
当n=2,3,5,7时,M n 都是素数,但n=11时,M n =M 11 =2 11 -1=2047=23X89,显然不是梅森素数。
1722年,瑞士数学大师欧拉证明了2 31 -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
Linux公社的RSS地址 : https://www.linuxidc.com/rssFeed.aspx
本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-11/155613.htm
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
程序员2010精华本
程序员杂志社 / 电子工业 / 2011-1 / 49.00元
《程序员(2010精华本)》主要内容:《程序员》创刊10年来,每年末编辑部精心打造的“合订本”已经形成一个品牌,得到广大读者的认可和喜爱。今年,《程序员》杂志内容再次进行了优化整合,除了每期推出的一个大型专题策划,各版块也纷纷以专题、策划的形式,将每月的重点进行了整合,让内容非常具有凝聚力,如专题篇、人物篇、实践篇等。另外杂志的版式、色彩方面也有了很大的飞跃,给读者带来耳目一新的阅读体验。一起来看看 《程序员2010精华本》 这本书的介绍吧!