if (2 ** (tester - 1)) % tester == 1: # Fermat's little theorem #
if prime_line.count(tester) == 0: #
prime_line.append(tester)
我正在使用一个程序,该程序接受任意值或字符串或其组合的多行输入,并返回该集合中任何存在的素数。我正在使用费马定理来测试数字是否为素数,以最大程度地减少处理时间。在上述代码中,诸如 194394788347 之类的数字已被去除其字母(起始输入为 1943jds9478cxbfhjvbfd8347),因此在进行指数计算时会产生内存错误。有什么办法可以解决这个问题吗?
最佳答案
2 ** 194394788347
是一个天文数字,光是存储就需要超过 22 GB。幸运的是,python 包含一个函数,可以在执行模数时取幂:pow(base, exp, mod) .
if pow(2, tester - 1, tester) == 1:
这也快得多,因为没有一个中间数比模数大很多。
关于python - 我的素数程序中的指数抛出内存错误,我该如何解决?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59060318/