C语言求梅森素数代码及解析

栏目: C · 发布时间: 5年前

内容简介:梅森数(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不是梅森素数。

程序流程图:

C语言求梅森素数代码及解析 下面是完整的代码

​#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

C语言求梅森素数代码及解析

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-11/155613.htm


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Responsive Web Design

Responsive Web Design

Ethan Marcotte / Happy Cog / 2011-6 / USD 18.00

From mobile browsers to netbooks and tablets, users are visiting your sites from an increasing array of devices and browsers. Are your designs ready? Learn how to think beyond the desktop and craft be......一起来看看 《Responsive Web Design》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

SHA 加密
SHA 加密

SHA 加密工具