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.
A good, fast way to find primes.
n
is the upper limit to stop searching.Here's a fast and clear imperative prime generator not using sieves:
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.Very nice! You just forgot to stop taking primes from the inner
genPrimes()
when the square root ofx
is reached. That's all.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...).
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:
Note that this is optimized for simplicity and clarity rather than performance.
Just a bit more concise:
And you can use it like this:
Here is a script that generates list of prime number from 2 to given number
This is just another implementation of Sieve of Eratosthenes.