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

生成素数的最快方法是使用筛子。这里我们使用 Eratosthenes 的分段筛来生成素数，一个一个没有最大值，按顺序生成；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

一个简单的isPrime使用试除法就足够了，因为它将被限制为n的第四个根。段大小2 * delta任意设置为 100000。此方法需要 O(sqrt n ) 空间用于筛分素数以及用于筛子的恒定空间。

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 回答
8

genPrimes()无条件地用完全相同的参数调用自己。这导致无限递归。

这是使用（非递归）生成器的一种方法：

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 回答
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 回答
1

再简洁一点：

import itertools

def check_prime(n, primes):
    for p in primes:
        if not n % p:
            return False
    return True

def prime_sieve():
    primes = set()
    for n in itertools.count(2):
        if check_prime(n, primes):
            primes.add(n)
            yield n

你可以像这样使用它：

g = prime_sieve()
   g.next()
=> 2
   g.next()
=> 3
   g.next()
=> 5
   g.next()
=> 7
   g.next()
=> 11
于 2014-12-16T17:31:13.757 回答
1

非常好！genPrimes()当达到平方根时，您只是忘记停止从内部取素数x。就这样。

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

没有它，你就会滑出深渊，或者是什么表情。当蛇吃自己的尾巴时，它必须停在中间。如果它到达它的头，就没有更多的蛇了（好吧，这里吃的方向相反，但它仍然适用......）。

于 2013-03-30T07:18:34.330 回答
1

这是一个生成从 2 到给定数字的素数列表的脚本

from math import sqrt
next = 2
n = int(raw_input())
y = [i for i in range(2, n+1)]
while y.index(next)+1 != len(y) and next < sqrt(n):
    y = filter(lambda x: x%next !=0 or x==next, y)
    next = y[y.index(next)+1]
print y

这只是埃拉托色尼筛法的另一种实现。

于 2015-06-20T14:35:36.083 回答