1

次の素数を見つけるための高速でメモリ効率の良い方法を探しています。

入力:整数n

次の値より大きい最初の素数を出力n

nN 未満のすべての素数を一覧表示するFastest wayよりも小さいすべての素数を出力する、非常に優れたコードがあります。私の非効率的な方法は、現在、リストをループするだけで、より小さいすべての素数を見つけて2nから、より大きい最初の素数を検索します。nこれが私の現在のコードです。

import numpy
def primesfrom2to(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = numpy.ones(n/3 + (n%6==2), dtype=numpy.bool)
    for i in xrange(1,int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[       k*k/3     ::2*k] = False
            sieve[k*(k-2*(i&1)+4)/3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]

n=10**7
timeit next(x for x in primesfrom2to(2*n) if x > n)
1 loops, best of 3: 2.18 s per loop

n= 10**8
timeit next(x for x in primesfrom2to(2*n) if x > n)
1 loops, best of 3: 21.7 s per loop

この最後のテストには、ほぼ 1 GB の RAM が必要です。このコードのもう 1 つの問題は、たとえば $n = 10**10$ の場合に失敗することです。

この問題はより速く解決できますか? メモリの使用量を少なくする方法はありますか?

4

3 に答える 3

2

どうやら次のようにするのが最善の方法です。

  1. 小さな素数を含む数を排除するnまでふるいを開始します。2n
  2. Miller-Rabin などの確率的素数テスターを残りの値に対して実行します。
  3. 必要に応じて、素数と報告された最初の数に対して決定論的素数テスターを実行します。
于 2013-02-24T10:29:21.297 に答える
1

私は間違いなくある種のふるいまたはフィルターをお勧めします.

ファンジーの素数に関する問題を解決しようとしているときに、Python で次のコードを作成しました: https://gist.github.com/anonymous/4960155

IIRC では、約 15 秒で数百万の素数を処理できます。少し前のことです。保存できてよかったです！

于 2013-02-15T12:40:29.883 に答える
1

これを回避するには2つの方法が考えられます。私が最近試した最初のもの - C++ で非常に効率的なエラトステネスのふるいを作成し、それをC/C++ Extension for Python にしました。

s の実際の配列の代わりにビットマップを使用するため、メモリ効率が高く、int非常に高速です。最大 10**9 の場合、ビートアップした 1 コアの仮想マシンで約 20 秒間動作します (ビットマップを実際の int にエクスポートします)。 ）。あなたの場合、ビットマップのみを保持できます。今なら絶対最大値をn素数を事前計算できます。

もう 1 つのアプローチは、いくつかのPrimality テストを調べることですが、それらのいくつかは確率的であることを忘れないでください。

于 2013-02-15T12:27:45.583 に答える