Python 使用 Lucas-Lehmer 序列查找梅森素数并存储它们

Question

如果您正在寻找原始帖子，请点击下面我的个人资料图片旁边的蓝色“编辑[日期]”按钮。

由于 Stack Overflow 决定与 OpenAI 合作，我删除了这篇文章。 这一举措窃取了所有为 Stack Overflow 做出贡献的人的劳动成果，而且无法选择退出。 OpenAI 有着在网络上充斥不准确信息的历史 - 看看任何新闻文章，其中一半是 AI 生成的 SEO 优化垃圾 - 并且明确表示他们永远不会为原始创作者的工作付费。 [大部分复制自@benui]

如果您是版主 - 继续，恢复此编辑并禁止我。我将立即通过电子邮件向您发送 GDPR 删除请求。

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

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