使用Python求指数为20以内的所有梅森素数

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

一、梅森素数

梅森数（M_n）指的是形如2ⁿ - 1的正整数，其中指数 n 是素数。

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

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

目前仅发现 51 个梅森素数，最大的是 M_82589933 （即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，再下一个，武林网VEVB没找出来，指数是不是在100以内也不知道。

三、说明

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

本文（完）