Python实现查找第n个默尼森数的算法详解

宋时安

发布时间：2026-10-13| 4人浏览过

原创

本文介绍如何使用Python查找第n个默尼森数。默尼森数定义为满足M=2^P-1且P和M均为素数的数。文章详细解析了素数检测算法，通过遍历从2到平方根的因子来判断质数，并结合循环计算M值，筛选出符合条件的默尼森数及其对应的素数P，最终输出指定序号的结果。

默尼森数的定义与示例

这是一个经典的程序设计挑战：寻找第n个默尼森数。若存在素数P和M，且满足等式M=2^P-1，则M被称为默尼森数。例如，当P=5时，计算M=2^5-1=31。由于5和31均为素数，因此31是一个默尼森数（它是第3个默尼森数）。

程序功能模块设计

该程序的设计主要包含两个核心部分：首先是实现素数判断功能，其次是编写逻辑以输出第n个默尼森数。

素数检测与循环算法逻辑

在素数判断方面，依据定义，只需检测从2到该数平方根之间是否存在因子；若存在因子，则不是素数。在获取默尼森数方面，通过循环计算M=2^P-1的值，并调用上述素数判断函数进行验证，从而完成目标。

Python代码实现


from math import sqrt,pow
 
def prime(num):
  """检测num是不是质数"""
  k = sqrt(num)
  for i in range(2,int(k+1)):
    if num % i == 0:
      return False
  
  return True
 
def monisen(no):
  """找出第no个莫尼森数"""
  n = 0
  num = 2
  while n < no:
    m = pow(2,num) - 1
    if prime(num) == True and prime(m) == True:
      # 只有num和m都为质数时,n才会加一,即n是莫尼森数的序号
      n += 1
    num += 1
  return int(m),num-1
 
# 输出前五个莫尼森数M 以及对应的质数P
for i in range(1,6):
  print(monisen(i))