Python- Sieve of Eratosthenes- Compact Python

Question

This is my code for finding primes using the Sieve of Eratosthenes.

list = [i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)]  

for i in list:
    for a in list:
            if a!=i and a%i == 0:
                list.remove(a)

Trying to find a way to compress those nested for loops into some kind of generator or comprehension, but it doesn't seem that you can apply a function to a list using a comprehension. I tried using map and filter, but I can't seem to get it right.

Thinking about something like this:

print map(list.remove(a), filter(lambda a, i: (a%i ==0 and a!=i), [(a, i) for i in list for a in list])

Obviously doesn't work for a dozen reasons. If I just was using the filter portion of that code:

filter(lambda a, i: (a%i ==0 and a!=i), **[(a, i) for i in list for a in list]**

What's the proper way of putting two variables into the lambda? (a,i) makes it a tuple, but I want to submit 'a' and 'i' as independent variables to put into the lambda.

I ended up resolving the problem with this one-liner:

print sorted(set([i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)]).difference(a for i in l for a in l if a!=i and a%i == 0))

Answer 1

The first thing to note is that what you have written is not the sieve of eratosthenes. Look how many loops a totally naive sieve of eratosthenes executes:

def sieve1(n):
    loops = 0
    numbers = set(range(2, n))
    for i in range(2, int(n ** 0.5) + 1):
        for j in range(i * 2, n, i):
            numbers.discard(j)
            loops += 1
    return sorted(numbers), loops

Tested:

>>> sieve1(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 
 178)

178 loops for 100 numbers (not including the sort). This can be improved with a few minor changes:

def sieve2(n):
    loops = 0
    numbers = range(0, n)
    for prime in numbers:
        if prime < 2:
            continue
        elif prime > n ** 0.5:
            break
        for i in range(prime ** 2, n, prime):
            numbers[i] = 0
            loops += 1
    return [x for x in numbers if x > 1], loops

Tested:

>>> sieve2(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 
 102)

102 loops for 100 numbers (not including the filter at the end). Now look at yours:

def sieve3(n):
    loops = 0
    numbers = range(2, n)
    for i in numbers:
        for j in numbers:
            if j != i and j % i == 0:
                numbers.remove(j)
            loops += 1
    return numbers, loops

Tested:

>>> sieve3(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 
 663)

It gets worse:

>>> [sieve1(x)[1] for x in [100, 1000, 10000]]
[178, 2978, 41723]
>>> [sieve2(x)[1] for x in [100, 1000, 10000]]
[102, 1409, 16979]
>>> [sieve3(x)[1] for x in [100, 1000, 10000]]
[663, 28986, 1523699]

At n = 10000, your implementation does almost 100x as much work!

My suggestion would be to create a sensible implementation before making it "compact." Code golf can be fun, but it's nowhere near as challenging or as edifying as writing efficient code, whatever the length.

That said, consider this one-liner (if you don't count the import, which you could get rid of by using lambda x, y: x - y in place of operator.sub). This implements the first algorithm with a small improvement:

>>> from operator import sub
>>> reduce(sub, (set(range(x ** 2, 100, x)) for x in range(2, int(100 ** 0.5) + 1)), set(range(2, 100)))
set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])

Answer 2

It's not precisely a direct translation of your loops, but it's quite close and compact:

>>> l = range(2, 101)
>>> sorted(set(l).difference(a for i in l for a in l if a!=i and a%i == 0))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Although I'd suggest a > i rather than a != 0 as being shorter and faster ;)

Answer 3

You are not doing the Sieve of Eratosthenes; the danger of not properly implementing the algorithm is that it will be extremely slow. Try your algorithm on 10**6 for example.

Shortest implementation of the bounded Sieve of Eratosthenes I can come up with:

def primes(upTo):
    isPrime = list(range(upTo))
    for p in range(2,int(upTo**0.5)+1): #p: 2,3,4,...,sqrt(N)
        print(p, isPrime[p])
        if isPrime[p]:
            for multiple in range(p**2,upTo,p): #mult: p^2, p^2+p, p^2+2p, ..., N
                isPrime[multiple] = False
    return [x for x in isPrime[2:] if x]

Demo:

>>> list(primes(29))
[2, 3, 5, 7, 11, 13, 17, 19, 23]

It's actually rather succinct, if you ignore linebreaks and the massive skip-even-numbers optimization:

isPrime=[True]*upTo for p in range(2,upTo): if isPrime[p]: yield p for m in range(p,upTo,p): isPrime[m]=False

Answer 4

Here is the most compact true sieve I have come up with so far. This performs surprisingly well.

def pgen(n): # Sieve of Eratosthenes generator
    np = set() # keeps track of composite (not prime) numbers
    for q in xrange(2, n+1):
        if q not in np:
            yield q
            np.update(range(q*q, n+1, q))

>>> list(pgen(100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97]            

This slightly more complex version is the fastest I have seen:

def pgen(n): # Sieve of Eratosthenes generator by Dan Salmonsen
    yield 2
    np = set()
    for q in xrange(3, n+1, 2):
        if q not in np:
            yield q
            np.update(range(q*q, n+1, q+q))            

Here is a true sieve as a list comprehension:

def primes(n):
    sieve = set(sum([range(q*q, n+1, q+q) for q in odds], []))
    return [2] + [p for p in odds if p not in sieve]

>>> primes(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97]            

Answer 5

Not exactly the the most compact solution, but the step argument in the range function in Python3 helps here -

prime_sieve = [True] * (int(input('Primes Upto ?'))+1)
# The first prime number
for i in range(2, len(prime_sieve)):
    if prime_sieve[i]:
        for j in range(i+i, len(prime_sieve), i):
            prime_sieve[j] = False
        print(i, end=',')

Answer 6

The following one-liner is not related at all to your code:

def primes(n):
    return set(range(2,n))-{c for i in range(2,n) for c in range(2*i,n,i)}

Like your code, this is still not really the Sieve of Eratosthenes because, for example, it will futilely try to cross off multiples of 6 and 9 etc. Nevertheless it still runs significantly faster than most other Sieve look-alikes for values less than a million or more, since for small N there are "about as many" primes as non-primes (the fraction of numbers < N that are prime is 1/log(N)).

Heavily modified from source, possibly less efficient than original: http://codeblog.dhananjaynene.com/2011/06/10-python-one-liners-to-impress-your-friends/

Answer 7

Here's a simple demonstration of the sieve. Note that lambda isn't used as the filtering function, because the prime number needs to bound at definition time. Also of interest is that it's efficient in the sense of not duplicating divisions, but in the long run it could lead to you-know-what.

import itertools

def primes():
    ints = itertools.count(2)
    while True:
        p = next(ints)
        yield p
        ints = itertools.ifilter(p.__rmod__, ints)

print list(itertools.islice(primes(), 10))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Answer 8

def sieve(n):
    sieve_list = range(n)
    zero_list = [0] * n
    for i in range(2, int(n**.5) + 1):
        if sieve_list[i]:
            sieve_list[2*i:n:i] = zero_list[2*i:n:i]
    return filter(None, sieve_list)[1:]