使用C語言怎么求梅森素數

今天就跟大家聊聊有關使用C語言怎么求梅森素數，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

C語言是什么

C語言是一門面向過程的、抽象化的通用程序設計語言，廣泛應用于底層開發，使用C語言可以以簡易的方式編譯、處理低級存儲器。

問題描述

梅森數（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:%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

看完上述內容，你們對使用C語言怎么求梅森素數有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。