1

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

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函数的输入也必须是质数。

4

1 回答 1

0

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

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

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!")

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

于 2020-12-05T05:32:04.337 回答