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.

3 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
  3. This professional hacker is absolutely reliable and I strongly recommend him for any type of hack you require. I know this because I have hired him severally for various hacks and he has never disappointed me nor any of my friends who have hired him too, he can help you with any of the following hacks:

    -Phone hacks (remotely)
    -Credit repair
    -Bitcoin recovery (any cryptocurrency)
    -Make money from home (USA only)
    -Social media hacks
    -Website hacks
    -Erase criminal records (USA & Canada only)
    -Grade change
    -funds recovery

    Email: onlineghosthacker247@ gmail .com

    ReplyDelete