# Python prime number generator

I'm trying to get a better grasp on generators in Python because I don't use them enough (I think generators are cool). To do so I wrote a generator for prime numbers:

def primes():
x = 2
while True:
for y in xrange(2, x/2 + 1):
if x % y == 0:
break
else:
yield x
x = x + 1


This works as expected but if I use list comprehension to create a list of primes using this generator it's really slow when compared to sieve function that generates the same list:

[prime.next() for i in xrange(1000)] # exectues in 0.212 sec, sieve in 0.001 sec


I'm assuming that this is not the intended purpose of a generator, but I thought I would see if anyone can think of a way to make this faster.

• I can't come up with a proper answer at the moment but you should look into using memoization and a different algorithm here. Commented Dec 10, 2011 at 20:05

Stylistically, using itertools.count() rather than implementing your own counter would be a bit cleaner.

I also prefer using the any() over a generator rather than an explicit for loop with a break and else. I think it's easier to follow.

Algorithmically, the sieve has a big advantage because it uses the previously calculated primes to make checking the next prime faster. You don't need to check every number for divisions, just the primes. You could do something like:

past_primes = []
for x in itertools.count(2):
if not any(x % prime == 0 for prime in past_primes):
past_primes.append(x)
yield x


Performing the division will still be more expensive than what the sieve has to do. You could implement the entire sieve algorithm in a generator. But I'm not sure what purpose that would serve.

Generally, generators work nicely when you don't have to maintain a lot of state for each value generated. But that's not the case for primes.

• It's not really necessary to test divisibility by all past primes, only by ones up to sqrt(x). Commented Dec 17, 2011 at 17:37

I prefer using set instead of list in this case:

past_primes = set()
for x in itertools.count(2):
if not any(x % prime == 0 for prime in past_primes):