python - 这种素数筛的实现是否适用于所有素数？还是只是侥幸（Python）

Question

p = 2
for i in range(3,10000000000000000,2):
    if p%i >= 1:
        print(i)
        p = p*(i*i)

我已经对其进行了测试，它似乎至少可以在前 100 个素数上工作，它会准确地无限期地返回素数吗？（理论上不是字面意思）。

Answer 1

您的限制（除了代码正确性，注释已经指出）将基于 Python 允许的最大整数。事实证明，Python 在理论上具有无限的整数精度——受内存限制。

https://docs.python.org/2/library/stdtypes.html#numeric-types-int-float-long-complex

有四种不同的数字类型：普通整数、长整数、[...]。纯整数（也称为整数）在 C 中使用 long 实现，这为它们提供了至少 32 位的精度（sys.maxint 始终设置为当前平台的最大纯整数值，最小值为 -sys.maxint - 1）。长整数具有无限精度。[...]

因此，如果您使用 sys.maxint 并增加它，您仍然会得到一个整数：

In [6]: sys.maxsize ** 10
Out[6]: 4455508415646675013373597242420117818453694838130159772560668808816707086990958982033203334310070688731662890013605553436739351074980172000127431349940128178077122187317837794167991459381249L

但是，一旦超出 sys.maxsize，就会有性能损失。