C語言實現(xiàn)求梅森素數(shù)的代碼與解析
問題描述
梅森數(shù)(Mersenne Prime)指的是形如2n-1的正整數(shù),其中指數(shù)n是素數(shù),即為Mn。如果一個梅森數(shù)是素數(shù),則稱其為梅森素數(shù)。例如22-1=3、23-1=7都是梅森素數(shù)。
當n=2,3,5,7時,Mn 都是素數(shù),但n=11時,Mn=M11=211-1=2047=23X89,顯然不是梅森素數(shù)。
1722年,瑞士數(shù)學大師歐拉證明了231-1=2147483647是一個素數(shù),它共有10位數(shù),成為當時世界上已知的最大素數(shù)。
迄今為止,人類僅發(fā)現(xiàn)了47個梅森素數(shù)。梅森素數(shù)歷來都是數(shù)論研究中的一項重要內(nèi)容,也是當今科學探索中的熱點和難點問題。
試求出指數(shù)n<20的所有梅森素數(shù)。
問題分析
要編程求解的問題是找出指數(shù)n<20的所有梅森素數(shù)。根據(jù)梅森素數(shù)的定義,我們可以先求出n<20的所有梅森數(shù),再逐一判斷這些數(shù)是否為素數(shù)。如果是素數(shù),則表示該數(shù)為梅森素數(shù),打印輸出即可;否則不是梅森素數(shù)。
算法設計
要求出n<20的所有梅森數(shù),因此在本題的算法設計中需要釆用循環(huán)結(jié)構(gòu)。
設變量mp存儲梅森數(shù),整數(shù)i表示指數(shù),其取值從2〜19,i每變化一次,都相應的計算出一個梅森數(shù),存放在mp中。對每次計算得到的當前mp值,都調(diào)用函數(shù)prime()進行判斷。
在判斷mp是否為素數(shù)時,可以定義一個函數(shù)prime(),每次都將mp的當前值作為實參傳遞給函數(shù)prime(),并判斷是否為素數(shù)。如果n為素數(shù),則prime()函數(shù)返回值為1,否則prime()函數(shù)返回值為0。
若prime()函數(shù)返回值為1,則當前mp為梅森素數(shù),應該將其輸出;若prime()函數(shù)返回值為0,則當前mp不是梅森素數(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; }
運行結(jié)果:
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
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值,如果有疑問大家可以留言交流,謝謝大家對腳本之家的支持。
相關文章
C++數(shù)據(jù)結(jié)構(gòu)之單鏈表
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之單鏈表,鏈表是由一個個結(jié)點鏈結(jié)成的。結(jié)點包括數(shù)據(jù)域和指針域兩部分,數(shù)據(jù)域用來存儲數(shù)據(jù)元素的信息,指針域用來存儲下一個結(jié)點的地址,更詳細內(nèi)容請需要的小伙伴參考下面文章內(nèi)容2022-01-01C++實現(xiàn)CreatThread函數(shù)主線程與工作線程交互的方法
這篇文章主要介紹了C++實現(xiàn)CreatThread函數(shù)主線程與工作線程交互的方法,是Windows應用程序設計中非常實用的方法,需要的朋友可以參考下2014-10-10c++?創(chuàng)建型設計模式工廠方法Factory?Method示例詳解
這篇文章主要為大家介紹了c++?創(chuàng)建型設計模式工廠方法Factory?Method示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09