CODEWITHSUNDEEP
generatorpythonprimes
Rusty Rob
Rusty Rob

Reputation: 17193

is this primes generator pythonic

Is the following code for generating primes pythonic?

def get_primes(n):
    primes=[False,False]+[True]*(n-1)
    next_p=(i for i,j in enumerate(primes) if j)
    while True:
        p=next(next_p)
        yield p
        primes[p*p::p]=[False]*((n-p*p)//p+1)

Note that next(next_p) will eventually throw a StopIteration error which somehow ends the function get_primes. Is that bad?

Also note that next_p is a generator which iterates over primes, however primes changes during iteration. Is that bad style?

adding the following if statement gets it under 0.25 seconds for the first million primes:

if p*p<=n:
    primes[p*p::p]=[False]*((n-p*p)//p+1)

Upvotes: 5

Views: 518

Answers (3)

wim
wim

Reputation: 363043

There is nothing wrong with the StopIteration, indeed that is the expected behaviour for generators.

I would say this implementation is more pythonic (not necessarily more efficient):

def get_primes(n):
  """Generates prime numbers < n"""
  return (x for x in xrange(2,n) if all(x % i for i in xrange(2,x)))

Pythonic to me means clear, concise, readable, and using the strengths of the language. While I can see your implementation is some sort of sieve, I only know that from prior experience with those kind of algorithms. The implementation above I can read directly as a straight-forward test of divisibility.

Note: there is a minor difference in the interface, your implementation would yield primes <= n whereas my implementation would yield primes < n. Obviously this can be changed easily and trivially (just change n to n+1 in the function body), but I feel it is more pythonic to generate primes up-to-but-not including n to be more consistent with the way, say, range() builtin works.

EDIT: JUST FOR FUN

Here is a least pythonic implementation, and probably pretty inefficient too :) 

def get_primes(n):
  import re
  return (x for x in xrange(2,n) if re.match(r'^1?$|^(11+?)\1+$', '1' * x) is None)

I call this the least pythonic because you would be scratching your head for some days to figure out how it works if you haven't seen this trick before!!

Upvotes: 2

Rusty Rob
Rusty Rob

Reputation: 17193

Here is another somewhat pythonic solution motivated by @wim, however you can see it is slightly slower than the first method.

def get_primes2(n):
    primes=[]
    for i in range(2,n+1):
        small_primes=(p for p in primes if p*p<=i)
        if all(i%p for p in small_primes):
            yield i
            primes.append(i)

import timeit
print(timeit.timeit("list(get_primes(10**5))",number=5,setup="from __main__ import get_primes")/5.0)
"0.0350940692182945"
print(timeit.timeit("list(get_primes2(10**5))",number=5,setup="from __main__ import get_primes2")/5.0)
"8.226938898658908"

Upvotes: 0

senderle
senderle

Reputation: 151057

It's not bad that next(next_p) throws a StopIteration error -- that's what a generator always does when it runs out of items!

Changing the length of a list while iterating over it is a bad idea. But there's nothing wrong with simply changing the contents. Overall, I think this is a rather elegant, if basic, seive.

One small observation: when you "cross out" the multiples of prime numbers, you'll find, if you think about it for a bit, that you don't have to start with p * 2. You can skip ahead to p ** 2.

Upvotes: 3

Related Questions