Нахождение простых чисел Мерсенна

Попытка найти простые числа Мерсенна с помощью Тест простоты Лукаса-Лемера:

n=int(input("Enter n to check if 2^n-1 is a prime:"))
a=4
for i in range(0,n-2):
    b=a**2
    a=b-2
    if i==n-3:
        c=(a)%((2**n) - 1)
        if c==0:
            print((2**n) - 1 ,"is a prime number")
            break
if c!=0:
    print((2**n) - 1 ,"is not a prime number")

Можете ли вы критиковать этот код? Очевидно, что он нуждается в улучшении, поскольку он не работает для п <= 2 и вычислительная мощность возрастает экспоненциально с увеличением n. Я изучаю питон меньше года, мне всего 15 лет, и я хотел бы получить отзывы об этой программе.

Изменить: путаница с n-2 и n-3 связана с тем, что мы должны проверить, есть ли (n-1) -й член в серии делится на л = 2 ^ п — 1 чтобы установить, что l — простое число Мерсенна. Но, как вы могли заметить, в приведенном выше коде 0-й член рассматривается как 14, что является 3-м термином в фактическом ряду. Это означает, что существует разрыв в два члена между фактическим рядом и рядом, полученным программой, поэтому, чтобы фактически изучить (n-1) -й член в серии, мы должны рассмотреть (n-3) -й член здесь . Следовательно, беспорядок, который не позволяет n быть <= 2.

Выскажите свое мнение по этому поводу

1 ответ
1

Страница, на которую вы ссылаетесь, имеет псевдокод, и он s = ((s × s) − 2) mod M. И прямо под псевдокодом написано:

Выполнение mod M на каждой итерации гарантирует, что все промежуточные результаты будут иметь самое большее p бит (в противном случае количество битов удвоится на каждой итерации).

Сделайте это, и это будет намного быстрее.

И лучше используйте те же имена переменных, что и на странице, на которую вы ссылаетесь, не придумывайте новых, которые просто запутывают соединение.

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *