python - 我的素数程序中的指数抛出内存错误，我该如何解决？

Question

if (2 ** (tester - 1)) % tester == 1:  # Fermat's little theorem      #
    if prime_line.count(tester) == 0:                                 #
        prime_line.append(tester)

我正在使用一个程序，该程序接受任意值或字符串或其组合的多行输入，并返回该集合中任何存在的素数。我正在使用费马定理来测试数字是否为素数，以最大程度地减少处理时间。在上述代码中，诸如 194394788347 之类的数字已被去除其字母(起始输入为 1943jds9478cxbfhjvbfd8347)，因此在进行指数计算时会产生内存错误。有什么办法可以解决这个问题吗？

Answer 1

2 ** 194394788347 是一个天文数字，光是存储就需要超过 22 GB。幸运的是，python 包含一个函数，可以在执行模数时取幂:pow(base, exp, mod) .

if pow(2, tester - 1, tester) == 1:

这也快得多，因为没有一个中间数比模数大很多。