Wednesday, 2 March 2011

Finding prime numbers using Python sets

Prompted by this blog I did some experiments to see whether it was convenient to implement the sieve of Eratosthenes using Python sets.

What I came up with was decidedly slower (a factor two to be precise) but also a lot less convoluted than Ram's solution:

def sieve(n):
    a=range(1,n)
    return set(a)-{1}.union(*[set(a[i-1::i][1:]) for i in a[1:]])
The whole idea is to generate all sets of integer multiples for integers 2 and up. That is what set(a[i-1::i][1:] is all about. a is a list of integers starting at 1, so given an integer i, the slice a[i-1::i] will generate a list of all multiples of i. The minus one is to compensate for the fact the the list of integers does not start at zero.

This list of multiples except the first one is converted to a set. We actually generate a whole list of sets and the union of all these sets together with the set consisting of just the number one is subtracted from the set of all integers, leaving us with a set consisting only of prime numbers. Because the union method accepts individual set arguments only we expand the generated list of sets to separate argument with the asterisk * operator.

All considered I think this solutions is rather neat, even though its performance is not tremendous.

2 comments:

  1. In [6]: print sieve(79)
    set([2, 3, 5, 7, 41, 11, 73, 13, 47, 17, 37, 19, 53, 43, 23, 61, 67, 71, 59, 29, 31])

    ReplyDelete
  2. This one is a pretty pure sieve using sets, with decent performance too. http://code.activestate.com/recipes/117119-sieve-of-eratosthenes/#c16

    ReplyDelete