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

4 つの異なる数値型があります: 単純な整数、長整数、[...]。プレーン整数 (単に整数とも呼ばれる) は C で long を使用して実装され、少なくとも 32 ビットの精度が得られます (sys.maxint は常に現在のプラットフォームのプレーン整数の最大値に設定され、最小値は -sys.maxint です)。 - 1)。長整数の精度は無制限です。[...]

したがって、sys.maxint を取得してそれを増やしても、整数が得られます。

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

ただし、sys.maxsize を超えると、パフォーマンスが低下します。