这篇文章将要介绍梅森素数的定义以及在Python中实现的方法。

一、梅森素数

梅森数(Mn)指的是形如2n - 1的正整数，其中指数 n 是素数。

如果一个梅森数是素数，则称其为梅森素数。例如22-1=3、23-1=7都是梅森素数。

当n=2，3，5，7时，Mn都是素数，但n = 11时，Mn = M11 = 211 - 1 = 2047 = 23 × 89，显然 M11 不是梅森素数。

目前仅发现 51 个梅森素数，最大的是 M82589933 (即2的82589933次方减1)，有24862048位。

梅森素数历来都是数论研究中的一项重要内容，也是当今科学探索中的热点和难点问题。

(以上来自 @潘石屹 微博话题 #潘石屹用Python解决100个问题#)

二、在Python中的实现方法

以下是实现求指数 n < 20 以内的所有梅森素数的源代码。

import math

# 定义判断一个数是否为素数的函数

def

isprime(num):

tmp = int(math.sqrt(num))

for

i

in

range(2, tmp + 1):

if

num % i == 0:

return

False

return

True

N = 20  # 定义指数n的最大值

for

n

in

range(2, N + 1):

if

isprime(n): # 指数n是否为素数

mn = pow(2, n) - 1  # 求出梅森数

if

isprime(mn): # 梅森数也是素数，则输出

print(f"n={n}, M{n}={mn}")

以上程序执行的结果如下：

n=2, M2=3

n=3, M3=7

n=5, M5=31

n=7, M7=127

n=13, M13=8191

n=17, M17=131071

n=19, M19=524287从运行结果来看，指数为20以内的梅森素数共7个。你可以接着往下找，第8个是 M31 = 21 4748 3647，第9个是M61 = 230 5843 0092 1369 3951，再下一个，翔宇亭IT乐园没找出来，指数是不是在100以内也不知道。

三、说明

因为梅森素数很稀有，寻找起来也很费时，上面查找指数在20以内的梅森素数在个人电脑上约在1秒左右就可以完成。第8个约需要0.35秒，第9个约需130秒，下一个运行了很长时间，改进了求素数的算法，仍然没有找出来。下图是在运行多次后截图的情况：

本文(完)

如有其它好的算法，敬请推荐。

如需转载，请注明出处：翔宇亭IT乐园(http://www.biye5u.com/)

本文链接地址：http://www.biye5u.com/article/python/2020/6471.html