Prime sieves are common devices for generating prime numbers in a given range. These lists can be used for quick verification of relatively small prime numbers (typically ranging up to 10⁶ or greater), in particular when many such verifications may be necessary.

Etymology: A sieve¹⁾ is a physical metaphor (i.e., a mesh bowl in a kitchen) for an algorithmic technique used in number theory to “sift out” a class of numbers in a given set or range.

sieve.py

def sieve(n):
    assert n > 1
    primes = [True] * (n+1)
    primes[0] = primes[1] = False
    for i in range(2, int(sqrt(n))+1):
        for j in range(i**2, n+1, i):
            primes[j] = False
    return [i for i in range(len(primes)) if primes[i]]

The Sieve of Eratosthenes is not the fastest prime sieve available, but it is quick to code, easy to understand and modify, and sufficiently fast for some practical applications.

Time Complexity: O((n log n)(log log n))²⁾
Space Complexity: O(n)

This implementation should work reliably for primes up to 10⁶ in competition settings.