這個素數篩的實現是否適用於所有的素數？或者它只是一個僥倖（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。