2

例えば

f(2)->1
f(3)->2
f(4)->-1 //4 is not a prime
f(5)->3
...

一般に、素数ジェネレーターを作成し、x に達する前にカウントします

def f(x):
    p = primeGenerator()
    count=1
    while True:
        y = next(p)
        if y>x:
            return -1
        elif y==x:
            return count
        else:
            count+=1

遅すぎませんか?次の呼び出しのためにリストをキャッシュすることはできますが、入力が素数でなければならないことを保証する場合は、入力数値が素数であるかどうかをテストする必要はありません。答え？

4

2 に答える 2

3

最適な方法は、取得する入力と、関数が何度も呼び出されるか、1 回だけ呼び出されるか、数回呼び出されるかによって異なります。

頻繁に呼び出され、受け取るすべての入力が小さく、たとえば 10 7を超えない場合、最善の方法は、事前にルックアップ テーブルを作成し、入力をルックアップすることです。

頻繁に呼び出されず、すべての入力が小さい場合は、入力を超えない素数を生成してカウントするだけで十分です。最初の引数が 19394489 で、次の引数が 20889937 の場合、0 からやり直す必要はなく、次の引数の間の素数を見つけるだけでよいように、次の呼び出しのために既に持っているものを覚えておくのは拡張機能かもしれません。彼ら。ただし、追加のストレージを使用する価値があるかどうかは、渡された引数によって異なります。

それが頻繁に呼び出され、引数が大きすぎず、たとえば 10 13を超えない場合、最良の方法は、 のπ(n)いくつかの選択値のの値を事前計算しn、各引数について、次に小さい事前計算されたポイントの値を検索することです。次に、そのポイントとターゲット値の間の素数を生成してカウントします (または、ターゲットが次に大きな事前計算されたポイントに近い場合は、ターゲットとその間の素数を数えます)。

たとえば、10 13を超えない10 7π(n)のすべての倍数を計算すると、100 万エントリのルックアップ テーブルが得られます。これは、最近ではメモリにあまり負担をかけず、500 万を超える範囲をふるい分ける必要はありません。長い時間がかかります。

ルックアップ テーブルをディスク上のファイルまたはデータベースとして保持することもできます。これにより、事前計算されたポイント間の間隔がはるかに短くなります。これにより、起動時に事前計算されたテーブルを読み取る時間がなくなりますが、ルックアップにはファイル システムへのアクセスが含まれるため、メモリの読み取りよりもはるかに時間がかかります。最適な戦略は、予想される入力とそれが実行されるシステムによって異なります。

ただし、上限が小さくない場合、ルックアップ テーブルの計算にはかなりの時間がかかりますが、それは 1 回限りのコストです。

予想される入力がより大きく、たとえば最大 10 16であり、その範囲のルックアップ テーブルを事前計算するために必要な時間を費やす気がない場合、最善の策は素数カウント関数のより優れたアルゴリズムの 1 つを実装することです。Lehmer によって改良された Meissel の方法は、比較的簡単に実装できます (ここで実装例を示すほど簡単ではありませんが、Haskell の実装が役立つかもしれません)。Millerらによって改善された方法は、より優れていますが、より複雑です。

それを超えて、現在の最先端を調査する必要があり、おそらく Python よりも低レベルの言語を使用する必要があります。

于 2012-09-30T17:03:45.563 に答える
2

先行するすべての候補の素数をチェックする必要があります。近道はありません。おっしゃるとおり、前の計算の結果をキャッシュしてそこから開始することもできますが、実際にはそれが最善の方法です。

于 2012-09-30T00:20:25.110 に答える