Python 3 Sieve of Eratosthenes - https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif

sieve.py

from itertools import count, takewhile
from math import sqrt
import time

try:
    # Python 2 compat
    from itertools import ifilter as filter
except ImportError:
    pass

try:
    # Python 2 compat
    range = xrange
except NameError:
    pass


def sieve_brevity_ad_absurdum(limit):
    candidates = set(range(2, limit + 1))

    loops = 0
    for n in candidates:
        loops += 1
        sieved = set(filter(lambda x: not x % n, candidates - {n}))
        # create new candidates object, for loop continues over the original
        candidates = candidates - sieved

    return sorted(candidates), loops

def sieve_absurder_brevity(limit):
    candidates = set(range(2, limit + 1))

    loops = 0
    # make a copy of candidates otherwise changing its size will cause
    # RuntimeError: Set changed size during iteration
    for n in set(candidates):
        loops += 1
        candidates &= {n} | set(filter(n.__rmod__, candidates))

    return sorted(candidates), loops


_loops = 0
def _sieve_itertools():
    global _loops
    candidates = count(2)

    _loops = 0
    while True:
        _loops += 1

        n = next(candidates)
        yield n

        # this needs to be wrapped in a function otherwise it fails to retain
        # the local variable context when later lazily run
        def filter_out_multiples(it, prime=n):
            return filter(lambda x: x % prime != 0, it)

        # compose a stack of iterators that each remove multiples of a prime
        candidates = filter_out_multiples(candidates, prime=n)

def sieve_itertools(limit):
    return list(takewhile(lambda x: x <= limit, _sieve_itertools())), _loops


def genuine_sieve_of_eratosthenes(limit):
    """ See https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf """
    candidates = set(range(2, limit + 1))

    loops = 0
    for n in candidates:
        if n > sqrt(limit):
            continue
        loops += 1
        # real sieve of eratosthenes!
        sieved = set(range(n * n, limit + 1, n))
        # create new candidates object, for loop continues over the original
        candidates = candidates - sieved

    return sorted(candidates), loops

if __name__ == '__main__':
    limit = 5000

    sieves = (
        sieve_brevity_ad_absurdum,
        sieve_absurder_brevity,
        sieve_itertools,
        genuine_sieve_of_eratosthenes,
    )
    for sieve in sieves:
        start = time.time()
        primes, loops = sieve(limit)
        end = time.time()
        print('{:>30} {:4d} loops, {:.4f}s, {} primes: [...{}'.format(
            sieve.__name__, loops, end - start, len(primes), str(primes)[-50:]))

time_complexity.py

"""
# python 2 only :-(
pip install big_o
"""

from sieve import (
    sieve_brevity_ad_absurdum,
    sieve_absurder_brevity,
    sieve_itertools,
    genuine_sieve_of_eratosthenes,
)

import big_o

sieves = (
    sieve_brevity_ad_absurdum,
    sieve_absurder_brevity,
    sieve_itertools,
    genuine_sieve_of_eratosthenes,
)

for sieve in sieves:
    best, rest = big_o.big_o(sieve, big_o.datagen.n_, min_n=10, max_n=10000)
    print '{:>27} {}'.format(sieve.__name__, best)