Python 用 Lucas-Lehmer 序列寻找 Mersenne 素数并存储它们

Question

我正在尝试在我的计算机上计算大素数（为了好玩）。到目前为止，我已经到了可以计算素数的地步。但是，我想知道如何存储它们并使它们在代码重新启动时从中断处继续。这是我的代码：

lucas_lehmer = [4]

def mersenne(n):
    return (2 ** n) - 1

def ll(n):
    global lucas_lehmer
    if len(lucas_lehmer) < n:
        for num in range(n-1):
            lucas_lehmer.append(lucas_lehmer[-1] ** 2 - 2)
    return lucas_lehmer[n-1]

def check_prime(n):
    m = mersenne(n)
    if ll(n - 1) % m == 0:
        return m
    else:
        return -1

它使用 Lucas-Lehmer 序列计算素数。该数列以 4 开头，下一个数字是数字的平方减 2。另外，check_prime 函数的输入也必须是质数。

Answer 1

您的算法足够慢，存储和重新启动不会有太大价值，因为它很快就会触底。但是，这仍然是一个很好的锻炼。

首先，您代码中的这一行不是最优的：

for num in range(n-1):

因为它可能会导致您向 lucas_lehmer 数组中添加更多项，而不是回答直接问题所需的项。它应该更像：

while len(lucas_lehmer) < n:

或者数组的长度和你正在测试的数字之间的差异。

根据我对这段代码的理解，您需要存储的不是质数，而是您的 lucas_lehmer 数组，这样您就不必在重新启动代码时再次构建它。这就是我在下面采用的方法：

图书馆lucas_lehmer.py

import pickle

PICKLE_FILE = "lucas_lehmer.pickle"

lucas_lehmer = None

def ll(n):
    global lucas_lehmer

    if lucas_lehmer is None:
        try:
            with open(PICKLE_FILE, 'rb') as file:
                lucas_lehmer = pickle.load(file)
        except FileNotFoundError:
            lucas_lehmer = [4]

    if len(lucas_lehmer) < n:
        while len(lucas_lehmer) < n:
            lucas_lehmer.append(lucas_lehmer[-1] ** 2 - 2)

        with open(PICKLE_FILE, 'wb') as file:
            pickle.dump(lucas_lehmer, file)

    return lucas_lehmer[n - 1]

def check_prime(n):
    mersenne = (2 ** n) - 1

    if ll(n - 1) % mersenne == 0:
        return mersenne

    return -1

此代码将为您创建 lucas_lehmer.pickle 文件（如果不存在）。我用 JSON 试过这个，但是对于大整数它比 Pickle 稍微慢一点。现在，您还需要启动、停止和重新启动的测试代码：

from lucas_lehmer import check_prime

def is_prime(n):
    if n < 2:
        return False

    if n % 2 == 0:
        return n == 2

    for divisor in range(3, int(n ** 0.5) + 1, 2):
        if n % divisor == 0:
            return False

    return True

while True:
    number = int(input("Enter a number: "))

    if number < 0:
        break

    if is_prime(number):
        print(number, check_prime(number))
    else:
        print(number, "not prime!")

这样做的关键是您需要检测您的库以确保它正确地初始化、加载和转储。

Python 用 Lucas-Lehmer 序列寻找 Mersenne 素数并存储它们

Python Finding Mersenne primes with Lucas-Lehmer sequence and storing them

python

primes