问题描述

梅森数（Mersenne Prime）指的是形如2ⁿ-1的正整数，其中指数n是素数，即为M_n。如果一个梅森数是素数，则称其为梅森素数。例如2²-1=3、2³-1=7都是梅森素数。

当n=2，3，5，7时，M_n 都是素数，但n=11时，M_n=M₁₁=2¹¹-1=2047=23X89，显然不是梅森素数。

1722年，瑞士数学大师欧拉证明了2³¹-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不是梅森素数。

程序流程图：
https://mmbiz.qlogo.cn/mmbiz_png/sMARbZtTY5fmmJqc62USYuOX9Ol7EhdjBGy7gjFCHbvftO6n2QMQs9UYagcY3zI1hMn2XozUMtX9r2Zgs4KSbw/0?wx_fmt=png

下面是完整的代码：

1. #include

2. #include

3. int prime(int n)

4. {

5. int i;

6. long k;

7. k=sqrt(n)+1;

8. for(i=2; i<=k; i++)

9. if(n%i == 0)

10. return 0;

11. return 1;

12. }

13. int main()

14. {

15. int mp, n=0, i;

16. printf("Mersenne Prime:\n");

17. for(i=2; i<=20; i++)

18. {

19. mp=pow(2,i)-1;

20. if( prime(mp) )

21. {

22. n++;

23. printf("M(%d)=%d", i, mp);

24. printf("\n");

25. }

26. }

27. printf("the number of Mersenne Prime less than 20 is:%d\n", n);

28. 
    

29. return 0;

30. }

运行结果：
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