Блог

Я пытаюсь вычислить большие простые числа (для развлечения) на своем компьютере. Пока я дошел до того, что он может вычислять простые числа. Однако мне интересно, как я могу их сохранить и сделать так, чтобы при перезапуске кода он продолжался с того места, где он остановился. Вот мой код:

 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
  

Он вычисляет простые числа, используя последовательность Лукаса-Лемера. Последовательность начинается с 4, а следующее число — это число в квадрате минус 2. Кроме того, входные данные check_prime функции также должны быть простым числом.

Ваш алгоритм достаточно медленный, поэтому сохранение и перезапуск не будут иметь большого значения, поскольку он быстро исчерпывается. Тем не менее, это все еще хорошее упражнение.

Во-первых, эта строка в вашем коде не является оптимальной:

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

Ключом к этому является то, что вам нужно настроить вашу библиотеку, чтобы убедиться, что она правильно инициализирует, загружает и выгружает.