這篇文章主要給大家介紹了關(guān)于利用C語言實(shí)現(xiàn)求梅森素?cái)?shù)的代碼與解析，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

問題描述

梅森數(shù)（Mersenne Prime）指的是形如2n-1的正整數(shù)，其中指數(shù)n是素?cái)?shù)，即為Mn。如果一個(gè)梅森數(shù)是素?cái)?shù)，則稱其為梅森素?cái)?shù)。例如22-1=3、23-1=7都是梅森素?cái)?shù)。

當(dāng)n=2，3，5，7時(shí)，Mn 都是素?cái)?shù)，但n=11時(shí)，Mn=M11=211-1=2047=23X89，顯然不是梅森素?cái)?shù)。

1722年，瑞士數(shù)學(xué)大師歐拉證明了231-1=2147483647是一個(gè)素?cái)?shù)，它共有10位數(shù)，成為當(dāng)時(shí)世界上已知的最大素?cái)?shù)。

迄今為止，人類僅發(fā)現(xiàn)了47個(gè)梅森素?cái)?shù)。梅森素?cái)?shù)歷來都是數(shù)論研究中的一項(xiàng)重要內(nèi)容，也是當(dāng)今科學(xué)探索中的熱點(diǎn)和難點(diǎn)問題。

試求出指數(shù)n<20的所有梅森素?cái)?shù)。

問題分析

要編程求解的問題是找出指數(shù)n<20的所有梅森素?cái)?shù)。根據(jù)梅森素?cái)?shù)的定義，我們可以先求出n<20的所有梅森數(shù)，再逐一判斷這些數(shù)是否為素?cái)?shù)。如果是素?cái)?shù)，則表示該數(shù)為梅森素?cái)?shù)，打印輸出即可；否則不是梅森素?cái)?shù)。

算法設(shè)計(jì)

要求出n<20的所有梅森數(shù)，因此在本題的算法設(shè)計(jì)中需要釆用循環(huán)結(jié)構(gòu)。

設(shè)變量mp存儲(chǔ)梅森數(shù)，整數(shù)i表示指數(shù)，其取值從2〜19，i每變化一次，都相應(yīng)的計(jì)算出一個(gè)梅森數(shù)，存放在mp中。對(duì)每次計(jì)算得到的當(dāng)前mp值，都調(diào)用函數(shù)prime()進(jìn)行判斷。

在判斷mp是否為素?cái)?shù)時(shí)，可以定義一個(gè)函數(shù)prime()，每次都將mp的當(dāng)前值作為實(shí)參傳遞給函數(shù)prime()，并判斷是否為素?cái)?shù)。如果n為素?cái)?shù)，則prime()函數(shù)返回值為1，否則prime()函數(shù)返回值為0。

若prime()函數(shù)返回值為1，則當(dāng)前mp為梅森素?cái)?shù)，應(yīng)該將其輸出；若prime()函數(shù)返回值為0，則當(dāng)前mp不是梅森素?cái)?shù)。

程序流程圖：

下面是完整的代碼：

#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;
}

運(yùn)行結(jié)果：