用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 seqence计算素数。序列从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!")

关键是您需要对您的库进行测试，以确保它正确地初始化、加载和转储。