C語言求梅森素數

03-17

梅森數（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: "); for(i=2; i<=20; i++) { mp=pow(2,i)-1; if( prime(mp) ) { n++; printf("M(%d)=%d", i, mp); printf(" "); } } printf("the number of Mersenne Prime less than 20 is:%d ", 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語言中文網實例精講http://c.biancheng.net/cpp/u/yuanma/，100個C語言實例免費與你分享！