数字が10億未満の数字のためにPythonで素数であるかどうかを素早く判断してください

Question

私の現在のアルゴリズムは、Pythonで数字の素数性をチェックする方法で、1000万〜私は10億を超える数字を得ることはないと知って改善したいと思っています。

プロジェクトの問題60を解決するのに十分速い実装を得ることができないということです。オイラー：私は60秒で75秒で問題の答えを得ています。 http://projecteuler.net/index.php?section=problems&id=60

私の処分ではメモリがほとんどないため、10億以下の素数はすべて格納できません。

私は現在、6k±1で調整された標準試行を使用しています。これ以上のものはありますか？私はすでにこれほど大きな番号のRabin-Millerメソッドを取得する必要がありますか？

primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 
def isprime(n): 
    if n <= 100: 
     return n in primes_under_100 
    if n % 2 == 0 or n % 3 == 0: 
     return False 

    for f in range(5, int(n ** .5), 6): 
     if n % f == 0 or n % (f + 2) == 0: 
      return False 
    return True 

このアルゴリズムを改善するにはどうすればよいですか？

精度：私はPythonを初めて使い、Python 3+のみで作業したいと考えています。

---

最終的なコード興味がある人のために

は、MAKのアイデアを使用して、私は私が以内にオイラーの問題の結果を取得することができ、およそ1/3迅速で、次のコードを生成しました60秒以上！

from bisect import bisect_left 
# sqrt(1000000000) = 31622 
__primes = sieve(31622) 
def is_prime(n): 
    # if prime is already in the list, just pick it 
    if n <= 31622: 
     i = bisect_left(__primes, n) 
     return i != len(__primes) and __primes[i] == n 
    # Divide by each known prime 
    limit = int(n ** .5) 
    for p in __primes: 
     if p > limit: return True 
     if n % p == 0: return False 
    # fall back on trial division if n > 1 billion 
    for f in range(31627, limit, 6): # 31627 is the next prime 
     if n % f == 0 or n % (f + 4) == 0: 
      return False 
    return True 

Answer 1

最大10^9の数値の場合、すべての素数をsqrt（10^9）まで生成してから、そのリストの数字に対する入力数の分割可能性を確認することができます。数字がその平方根以下の他の素数で割り切れない場合は、それ自身が素数でなければなりません（少なくとも1つの因子< = sqrtと素数ではない他の> = sqrtを持つ必要があります）。すべての数値の除算を、平方根（32,000ぐらい）までテストする必要はないことに注目してください。 sieveを使用して素数のリストを生成することができます。

probabilistic prime testに行くこともできます。しかし、それらは理解するのが難しいかもしれません。この問題のために、生成された素数リストを使うだけで十分です。

Answer 2

あなたはまず自分のnのみごprimes_under_100で割ることができます。

また、より多くの素数を計算します。

実際にはrange()の結果をメモリに保存しています。代わりにirange()を使用し、このメモリをSieve of Eratosthenes algorithmに使用してください。

Answer 3

Project Eulerの問題を解決するために、私はあなたの質問で提案したことを実行しました。Miller Rabinテストを実装します（C＃では、これはPythonで速くなると思われます）。アルゴリズムはそれほど難しいことではありません。 4,759,123,141以下の数字の場合は、数字が基底2,7,61に対して強い擬似素数であることを確認するだけで十分です。それを小数点による試行除算と組み合わせます。

これまでに解決した問題の数はわかりませんが、素早く素数性テストを行うことは、多くの問題に対して大きな価値があります。