Простые числа Мерсенна с использованием теста Лукаса-Лемера в Python - PullRequest
Новая
       13

Простые числа Мерсенна с использованием теста Лукаса-Лемера в Python

0 голосов
/ 15 апреля 2020

Я написал следующий код для присвоения номера Прайма Мерсенена, проверенного с помощью теста Лукаса-Лемера. Проблема в том, что код работает штрафом для простых чисел до 15, и если я превысил его, он продолжает работать. 

def is_prime(number):
    if number <= 1:
        return False

    for factor in range(2, number):
        if number % factor == 0:
            return False

    return True


mersenne = []

for number in range (3, 20):
    if is_prime (number):
        mersenne.append (2**number - 1)

primes = []
for i in range (3,20):
    if is_prime (i):
        primes.append (i)

print (primes)


def lucas_lehmer(number):
        M = 2**number - 1
        s = 4
        for _ in range(number-2):
            s = (s*s - 2) % M
        return True

lucas = []
for number in mersenne:
    if is_prime (number):
        if lucas_lehmer (number):
            lucas.append (1)
    else:
        lucas.append (0)

print (lucas)

mercenne_primes = zip (primes, lucas)

print (list (mercenne_primes))

1 Ответ

0 голосов
/ 20 апреля 2020

Ваш код обычно беспорядок. Но ваша главная, конкретная проблема c в том, что последняя строка вашей функции lucas_lehmer() неверна: 

return True

Это тест , он не может всегда возврат True! Последняя строка должна быть: 

return s == 0

Вот переписать ваш код, чтобы исправить вышеуказанную проблему, а также устранить ее: 

def is_prime(number):
    if number <= 1:
        return False

    if number % 2 == 0:
        return number == 2

    for factor in range(3, int(number ** 0.5) + 1):
        if number % factor == 0:
            return False

    return True

def lucas_lehmer(prime):
    s = 4
    m = 2 ** prime - 1

    for _ in range(prime - 2):
        s = (s * s - 2) % m

    return s == 0

mersenne_primes = [number for number in range(3, 1500) if is_prime(number) and lucas_lehmer(number)]

print(*mersenne_primes)

Вывод не в том же формате как ваш оригинал, но это легко исправить. Это с готовностью идет в 100 раз выше, чем ваш код: 

> python3 test.py
3 5 7 13 17 19 31 61 89 107 127 521 607 1279
>

Но, начав примерно в 200 раз, он станет заметно медленнее.

...