4

Python素数ジェネレーターを検索すると、次のことがわかりました。

def primes(n): 
    if n==2: return [2]
    elif n<2: return []
    s=range(3,n+1,2)
    mroot = n ** 0.5
    half=(n+1)/2-1
    i=0
    m=3
    while m <= mroot:
        if s[i]:
            j=(m*m-3)/2
            s[j]=0
            while j<half:
                s[j]=0
                j+=m
        i=i+1
        m=2*i+3
    return [2]+[x for x in s if x]

print primes(13)
print primes(3000)

また:

def get_primes(number):
    while True:
        if is_prime(number): #is_prime is defined somewhere else
            yield number
        number += 1

リストを返すのとyieldコマンドのどちらが効率的ですか? なんで？最初の 1000 個の素数など、非常に大量の素数を探しているとします。ところで、2 番目のコードは無限ループのようですが、どうすれば止められますか?

たくさんの質問をありがとう。

4

1 に答える 1

4

それは、素数のリストで何をしたいかによって異なります。

まず、Martijn が指摘したように、最初のアルゴリズムは非常に賢い素数ふるいであり、2 番目のアルゴリズムはすべての素数をテストします。高速素数アルゴリズムに興味がある場合は、アプローチをよりよく理解するために、いくつかの異なる素数ふるいを調べます。最も単純なのはエラトステネスのふるいです。

とにかく、それはあなたの質問ではないと思います。通常の Python 関数とジェネレーターの違いを本当に探しています。SO には多くの質問があり、ジェネレーターとは何かをよく説明するドキュメントがたくさんあります。

これは、あなたの質問を見ているときにサイドバーに表示されたもので、参考になると思います。または、ドキュメントで「ジェネレーター」を検索してください。

簡単な説明は、最初の関数が n までの素数のリストを返すことです。そのリストを取得したら、必要に応じてそのメンバーにアクセスしたり、リスト全体で関数を呼び出したりすることができます。2 番目のアプローチはジェネレーターです。これはリストを返しません。これは、要求に応じて次の素数を提示するイテレータを返します。そのため、素数が一度に 1 つずつ必要な場合、おそらく各素数で関数を呼び出すために、反復子が適している可能性があります。ただし、オンデマンドで素数にアクセスする必要がある場合は、これでは不十分です。

いくつかの基準を満たす最初の素数を探している場合は、範囲を指定する必要がないため、ジェネレーターが適しています。最初の 100 個だけが必要な場合、最初の 1000 個の素数を生成する理由はありません。

例えば：

for prime in get_primes(2):
    if meets_condition(prime):
        return prime

以下よりも優れています。

primeList = primes(1000)
for prime in primeList:
    if meets_condition(prime):
        return prime

n が小さい場合、ただし n が 1000 に近い場合はそうではありません。

行かなきゃ、ごめんなさい。後でこれを拡大して校正します。ジェネレーターとプライムシーブを調べてください！

projecteuler.com の問題に取り組んでいる場合は、ふるいの方がうまくいくと思います。

于 2013-07-01T02:08:19.427 に答える