sieve of eratosthenes implementation

[perfringo]

You can read wikipedia: Sieve of Eratosthenes.

In simple terms it is eliminating numbers which are not primes. Remaining numbers are primes.

Some dummy quick-and-dirty example to give general idea (skipped part where you actually find whether number is prime, provided in tuple):

- get numbers which are not primes
- get gaps between non-prime numbers (primes)

import heapq

def not_prime(max_value, stream=heapq.merge):
    """Yield non-primes under 100."""
    primes = (2, 3, 5, 7)    
    last = object()
    
    non_primes = (range(prime*2, max_value + 1, prime) for prime in primes)
    
    for el in stream(*non_primes):    # to eliminate duplicates
        if el != last:
            last = el
            yield el


def retrive_gaps(non_primes):
    "Yield gaps in non-prime numbers."
    last = 2
    yield last
    for x in non_primes:
        if x != last + 1:
            yield x - 1
        last = x

Practical usage is combining these two functions:

list(gap for gap in retrive_gaps(not_prime(100)))