如何用python迭代一个由长整数组成的列表？

Question

我想用python来迭代一个由长整数组成的列表（10位以上），但是用for-loop来做的时候，耗时较长，而且执行过程中shell-window会卡住。

例如：我有一个列表，如下所述。

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

我想在一个函数中对上述列表进行迭代，并使用 卢卡斯-莱默原始性检验 公式，并想用卢卡斯-莱默数列推导出布尔值，其中如果数字的p-2指数为0，则从 my_list 应视为质数，返回1(真)，否则0(假)

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 函数时，shell窗口在打印列表时崩溃。my_list

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

有什么办法可以加快迭代速度，同时我想打印出列表。prime_ll?

Answer 1

这段代码不会减少你的程序运行时间，但我想理论上应该会运行得更快。我基本上翻译了你引用的维基百科文章上的伪代码。

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. 当然，这还要加上你例子中的数字是大数量级的。

我还发现了一个 联系 包含你可能感兴趣的该算法的其他有效实现。