时间戳

首页 > 解决方案 > 如何编写一个函数 mersenne_prime，它接受参数 n_max 并返回 p 小于 n_max 的所有梅森素数 q 的列表？

python - 如何编写一个函数 mersenne_prime，它接受参数 n_max 并返回 p 小于 n_max 的所有梅森素数 q 的列表？

问题描述

梅森素数是那些数字 q = 2^p - 1 其中 p 和 q 都是素数。编写一个函数 mersenne_prime，它接受参数 n_max 并返回 p 小于 n_max 的所有梅森素数 q 的列表。提示：应该有 8 个梅森素数 p 小于 40。

我已经编写了以下代码，但是对于我输入 mersenne_prime(x) 的任何值，它产生的唯一输出是 3

def isprime(n):
  if n < 2:
    return False
  elif n == 2:
    return True
  else:
    if n % 2 == 0:
      return False
    for i in range(3,n,2):
      if n % i == 0:
        return False
    return True


def mersenne_prime(n_max):
  for i in range(1,n_max,1):
    q = 2**i-1
    if isprime(i) and isprime(q):
     print(q)

有没有人能够提供帮助来生成一个工作代码来生成梅森素数？

编辑：将返回函数更改为 print 适用于不同的输入值，但是在不同的系统中测试代码会产生错误消息。

Traceback (most recent call last):
  File "/home/runner/unit_tests.py", line 134, in test_mersenne_prime
    assert(len(mersenne_prime(4)) ==  len(correct_list)), \
TypeError: object of type 'NoneType' has no len()

标签： pythonfunctionprimes

解决方案

计算梅森素数的更好方法是使用 Lucas-Lehmer 检验：

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps

def lucas_lehmer(p):
    if p == 2: return True
    m, i, s = pow(2,p) - 1, 3, 4
    while i <= p:
        i, s = i+1, (pow(s,2) - 2) % m
    return s == 0

print [p for p in primes(256) if lucas_lehmer(p)]

打印出 [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127]，它们是小于 2**256 的梅森素数的索引。

推荐阅读