generator in Python generating prime numbers

2020-02-12 14:41发布

I need to generate prime numbers using generator in Python. Here is my code:

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

I have a RuntimeError: maximum recursion depth exceeded after the 2nd prime.next() when I run it.

7条回答
该账号已被封号
2楼-- · 2020-02-12 14:57

A good, fast way to find primes. n is the upper limit to stop searching.

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
查看更多
3楼-- · 2020-02-12 14:59

Here's a fast and clear imperative prime generator not using sieves:

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

It is almost identical to NPE's answer but includes a root test which significantly speeds up the generation of large primes. The upshot is the O(n) space usage for the primes list.

查看更多
劫难
4楼-- · 2020-02-12 15:07

Very nice! You just forgot to stop taking primes from the inner genPrimes() when the square root of x is reached. That's all.

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

Without it, you slide off the deep end, or what's the expression. When a snake eats its own tail, it must stop in the middle. If it reaches its head, there's no more snake (well, the direction of eating here is opposite, but it still applies...).

查看更多
爷的心禁止访问
5楼-- · 2020-02-12 15:09

genPrimes() unconditionally calls itself with exactly the same arguments. This leads to infinite recursion.

Here is one way to do it using a (non-recursive) generator:

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

Note that this is optimized for simplicity and clarity rather than performance.

查看更多
闹够了就滚
6楼-- · 2020-02-12 15:11

Just a bit more concise:

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

And you can use it like this:

g = prime_sieve()
   g.next()
=> 2
   g.next()
=> 3
   g.next()
=> 5
   g.next()
=> 7
   g.next()
=> 11
查看更多
放荡不羁爱自由
7楼-- · 2020-02-12 15:20

Here is a script that generates list of prime number from 2 to given number

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

This is just another implementation of Sieve of Eratosthenes.

查看更多
登录 后发表回答