Python prime number generator

Question

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.

• Jeff Mercado: I can't come up with a proper answer at the moment but you should look into using memoization and a different algorithm here.

Answer 1

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.

• UncleBens: It's not really necessary to test divisibility by all past primes, only by ones up to sqrt(x).

Answer 2

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):
 past_primes.add(x)
 yield x

Sets have better time complexity 0(1) vs O(n) of lists http://wiki.python.org/moin/TimeComplexity

• Winston Ewert: Nope. What's being done here is iteration which you'll see is O(n) for both lists and sets. Lists have lower overhead and thus will be more efficient here.