C语言达成求梅森素数代码解析
发布时间：2021-12-05 14:05:13 所属栏目：教程 来源：互联网
导读：问题描述 梅森数（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，显然不是梅森素数。
|
问题描述 梅森数（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:%dn", 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  （编辑：葫芦岛站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐