Comprehensions

Sieve
Sieve in Python 
def primes(number):
    prime = (item for item in range(2, number+1) 
              if item not in (not_prime for item in range(2, number+1) 
              for not_prime in range(item*item, number+1, item)))
    return list(prime)

Many of the solutions to Sieve use comprehensions or generator-expressions at some point, but this page is about examples that put almost everything into a single, elaborate generator-expression or comprehension.

The above example uses a generator-expression to do all the calculation.

There are at least two problems with this:

  • Readability is poor.
  • Performance is exceptionally bad, making this the slowest solution tested, for all input sizes.

Notice the many for clauses in the generator.

This makes the code similar to nested loops, and run time scales quadratically with the size of number. In fact, when this code is compiled, it compiles to nested loops that have the additional overhead of generator setup and tracking.

def primes(limit):
    return [number for number in range(2, limit + 1)
            if all(number % divisor != 0 for divisor in range(2, number))]

This second example using a list-comprehension with all() is certainly concise and relatively readable, but the performance is again quite poor.

This is not quite a fully nested loop (there is a short-circuit when all() evaluates to False), but it is by no means "performant". In this case, scaling with input size is intermediate between linear and quadratic, so not quite as bad as the first example.

13th Nov 2024 · Found it useful?

Other Approaches to Sieve in Python

Other ways our community solved this exercise
def primes(number):
    number += 1
    prime = [True for item in range(number)]
    for index in range(2, number):
        if not prime[index]: continue
        for candidate in range(2 * index, number, index):
            prime[candidate] = False
    return [index for index, value in enumerate(prime) if index > 1 and value]
Nested Loops

Relativevly clear solutions with explicit loops. 

def primes(number):
    not_prime = set()
    primes = []
    for num in range(2, number+1):
        if num not in not_prime:
            primes.append(num)
            not_prime.update(range(num*num, number+1, num))
    return primes
Set Operations

Performance enhancements with Python sets.