sieve.py

# Program collects all primes less than or equal n.
# It uses the Sieve of Eratosthenes algorithm, see
# https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


def primes(n):
    # Initializes start array with n-entries, all numbers are primes initially
    prime = [True for i in range(n + 1)]

    # 0 and 1 are no primes
    prime[0] = False
    prime[1] = False

    # start from 2 as first prime
    p = 2
    while p * p <= n:
        # number not crossed out yet, it must be a prime
        if prime[p] == True:
            # Cross out all multiples of p
            for i in range(p ** 2, n + 1, p):
                prime[i] = False
        p += 1

    # collect all primes, the numbers not crossed out
    return [i for i, v in enumerate(prime) if v]