Как написать функцию mersenne_prime, которая принимает аргумент n_max и возвращает список всех простых чисел Мерсенна q для p, меньших n_max? - PullRequest
Новая
       9

Как написать функцию mersenne_prime, которая принимает аргумент n_max и возвращает список всех простых чисел Мерсенна q для p, меньших n_max?

0 голосов
/ 05 марта 2020

Простыми числами Мерсенна являются те числа q = 2 ^ p - 1, где и p, и q простые. Напишите функцию mersenne_prime, которая принимает аргумент n_max и возвращает список всех простых чисел Мерсенна q для p, меньших n_max. Подсказка: должно быть 8 простых чисел Мерсенна с p меньше 40.

Я написал следующий код, но он выводит только 3 для любого значения, которое я вводил в mersenne_prime (x) 

def isprime(n):
  if n < 2:
    return False
  elif n == 2:
    return True
  else:
    if n % 2 == 0:
      return False
    for i in range(3,n,2):
      if n % i == 0:
        return False
    return True


def mersenne_prime(n_max):
  for i in range(1,n_max,1):
    q = 2**i-1
    if isprime(i) and isprime(q):
     print(q)

Кто-нибудь может предложить помощь в создании рабочего кода для генерации простых чисел mersenne?

Редактировать: Изменение функции возврата для печати работ для другого входного значения, однако тестирование кода в другая система выдает сообщение об ошибке. 

Traceback (most recent call last):
  File "/home/runner/unit_tests.py", line 134, in test_mersenne_prime
    assert(len(mersenne_prime(4)) ==  len(correct_list)), \
TypeError: object of type 'NoneType' has no len()

1 Ответ

0 голосов
/ 05 марта 2020

Лучший способ вычисления простых чисел Мерсенна использует тест Лукаса-Лемера: 

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps

def lucas_lehmer(p):
    if p == 2: return True
    m, i, s = pow(2,p) - 1, 3, 4
    while i <= p:
        i, s = i+1, (pow(s,2) - 2) % m
    return s == 0

print [p for p in primes(256) if lucas_lehmer(p)]

, который печатает [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 , 127], которые являются индексами простых чисел Мерсенна менее 2 ** 256.

...