C語言實現求梅森素數程式碼解析
問題描述
梅森數(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地址 : ofollow,noindex" target="_blank">https://www.linuxidc.com/rssFeed.aspx
本文永久更新連結地址: https://www.linuxidc.com/Linux/2018-11/155410.htm