4

Python でジェネレーターを使用して素数を生成する必要があります。これが私のコードです：

def genPrimes():
    yield 2
    x=2
    while True:
        x+=1
        for p in genPrimes():
            if (x%p)==0:
                break
        else:
            yield x

RuntimeError: maximum recursion depth exceeded after the 2nd prime. next() を実行すると発生します。

4

7 に答える 7

8

genPrimes()まったく同じ引数で無条件に自分自身を呼び出します。これにより、無限再帰が発生します。

(非再帰的) ジェネレーターを使用してそれを行う 1 つの方法を次に示します。

def gen_primes():
    n = 2
    primes = set()
    while True:
        for p in primes:
            if n % p == 0:
                break
        else:
            primes.add(n)
            yield n
        n += 1

これは、パフォーマンスよりも単純さと明快さのために最適化されていることに注意してください。

于 2013-03-29T16:10:54.730 に答える
8

素数を生成する最速の方法は、ふるいを使用することです。ここでは、セグメント化されたエラトステネスのふるいを使用して、素数を最大値なしで順番に 1 つずつ生成します。psは、現在の最大値より小さいふるい素数のリストであり、現在のセグメント内qsの対応する最小倍数のオフセットです。ps

def genPrimes():
    def isPrime(n):
        if n % 2 == 0: return n == 2
        d = 3
        while d * d <= n:
            if n % d == 0: return False
            d += 2
        return True
    def init(): # change to Sieve of Eratosthenes
        ps, qs, sieve = [], [], [True] * 50000
        p, m = 3, 0
        while p * p <= 100000:
            if isPrime(p):
                ps.insert(0, p)
                qs.insert(0, p + (p-1) / 2)
                m += 1
            p += 2
        for i in xrange(m):
            for j in xrange(qs[i], 50000, ps[i]):
                sieve[j] = False
        return m, ps, qs, sieve
    def advance(m, ps, qs, sieve, bottom):
        for i in xrange(50000): sieve[i] = True
        for i in xrange(m):
            qs[i] = (qs[i] - 50000) % ps[i]
        p = ps[0] + 2
        while p * p <= bottom + 100000:
            if isPrime(p):
                ps.insert(0, p)
                qs.insert(0, (p*p - bottom - 1)/2)
                m += 1
            p += 2
        for i in xrange(m):
            for j in xrange(qs[i], 50000, ps[i]):
                sieve[j] = False
        return m, ps, qs, sieve
    m, ps, qs, sieve = init()
    bottom, i = 0, 1
    yield 2
    while True:
        if i == 50000:
            bottom = bottom + 100000
            m, ps, qs, sieve = advance(m, ps, qs, sieve, bottom)
            i = 0
        elif sieve[i]:
            yield bottom + i + i + 1
            i += 1
        else: i += 1

nの 4 乗根に限定されるため、簡単なisPrime試行除算で十分です。セグメント サイズは任意に 100000 に設定されます。この方法では、素数をふるいに O(sqrt n ) のスペースと、ふるいに一定のスペースが必要です。2 * delta

isPrime低速ですが、ホイールを使用して素数候補を生成し、基数 2、7 、および 61 に対する強力な疑似素数テストに基づいて候補の素数性をテストするためのスペースを節約できます。これは 2^32 まで有効です。

def genPrimes(): # valid to 2^32
    def isPrime(n):
        def isSpsp(n, a):
            d, s = n-1, 0
            while d % 2 == 0:
                d /= 2; s += 1
            t = pow(a,d,n)
            if t == 1: return True
            while s > 0:
                if t == n-1: return True
                t = (t*t) % n; s -= 1
            return False
        for p in [2, 7, 61]:
            if n % p == 0: return n == p
            if not isSpsp(n, p): return False
        return True
    w, wheel = 0, [1,2,2,4,2,4,2,4,6,2,6,4,2,4,\
        6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,\
        2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    p = 2; yield p
    while True:
        p = p + wheel[w]
        w = 4 if w == 51 else w + 1
        if isPrime(p): yield p

素数を使ったプログラミングに興味がある場合は、私のブログでこのエッセイをお勧めします。

于 2013-03-29T19:17:23.750 に答える
2

素数を見つけるための優れた高速な方法。n検索を停止する上限です。

def prime(i, primes):
    for prime in primes:
        if not (i == prime or i % prime):
            return False
    primes.add(i)
    return i

def find_primes(n):
    primes = set([2])
    i, p = 2, 0
    while True:
        if prime(i, primes):
            p += 1
            if p == n:
                return primes
        i += 1
于 2013-03-29T16:11:37.740 に答える
2

これは、ふるいを使用しない高速で明確な命令型素数ジェネレーターです。

def gen_primes():
    n = 2
    primes = []
    while True:
        is_prime = True
        for p in primes:
            if p*p > n:
                break
            if n % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(n)
            yield n
        n += 1

これはNPEの回答とほぼ同じですが、大きな素数の生成を大幅に高速化するルート テストが含まれています。結果は、リストのO(n)スペース使用量ですprimes。

于 2015-05-08T10:35:30.897 に答える