def prime_sieve(n):
    """
    Return a list of all primes smaller than or equal to n.
    
    This algorithm uses a straightforward implementation of the 
    Sieve of Eratosthenes. For more information, see
    https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    
    Algorithmic details
    -------------------
    Memory: O(n)
    Time: O(n * log(log(n)))
    where n is the input number.
    
    Examples
    --------
    >>> prime_sieve(2)
    [2]
    >>> prime_sieve(9)
    [2, 3, 5, 7]
    >>> prime_sieve(30)
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    
    # Initialize the sieve
    is_prime = [True for i in range(n)]
    is_prime[0:1] = [False, False]
    
    for i in range(2, int(n**0.5 + 1)):

        # Keep going it it's not a prime
        if not is_prime[i]:
            continue

        # It's a prime number, remove all multiples larger than i * i
        c = i * i
        while c <= n:
            is_prime[c] = False
            c += i
               
    # Return a list of primes where True
    return list(num for (num, prime) in enumerate(is_prime) if prime)