Как перебрать список, состоящий из длинного целого значения, используя python? - PullRequest
Новая
       41

Как перебрать список, состоящий из длинного целого значения, используя python?

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

Я пытаюсь перебрать список, состоящий из длинного целого числа (более 10 цифр), но, делая это с for-l oop, это занимает больше времени, и окно оболочки застревает во время выполнения.

например: у меня есть список, как упомянуто ниже: 

my_list: [7,31,127,2047,8191,131071,524287,838607,536870911,2147483647]

, и я хочу повторить приведенный выше список в функции с формулой проверки лукас лемер формулой и хочу для получения логических значений с использованием ряда Лукаса Лемера, где, если число имеет 0 в своем индексе p-2, число из my_list следует рассматривать как простое число и возвращать 1 (True), иначе 0 (False) 

def ll_list(p):
    ll_myList = [4]
    for i in range(1,p-1):
          number = ((ll_myList[i-1])**2 -2) % (2**p - 1)
          ll_myList.append(number)
    #validating if the lucas-lehmer series (ll_myList) is a prime or not
    if ll_myList[p-2] == 0:
     return int(True)
    else:
     return int(False)

теперь, когда я вызываю функцию ll_list, окно оболочки вылетает при печати списка для каждого номера, упомянутого в my_list

prime_ll = [ll_list(i) for i in my_list]
print(prime_ll, '\n')

, есть ли способ ускорить итерацию и на в то же время я хочу напечатать список prime_ll?

1 Ответ

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

Этот код не сильно уменьшит время выполнения вашей программы, но я думаю, что теоретически он должен работать быстрее. Я в основном перевел псевдокод в статье Википедии, на которую вы ссылались. 

def lucas_lehmer(p):
    s = 4
    m = (1 << p) - 1
    for _ in range(p - 2):
        s = (s**2 - 2) % m
    return not s

Часть not s в основном проверяет, равен ли s 0. Если это так, not s вернет True; False в противном случае.

Причина, по которой этот код занимает так много времени, состоит в том, что в игре есть два цикла for: один в функции lucas_lehmer и один, проходящий через каждый элемент в my_list. Конечно, это связано с тем, что числа в вашем примере велики на порядки.

Я также нашел ссылку , содержащую другие эффективные реализации этого алгоритма, которые могут вас заинтересовать.

...