204. Count Primes

def count_primes(n):
    """Obvious intuition but too slow beyond n = 10*5, whereas n <= 5*106."""
    primes = set()
    if n >= 3:
        primes.add(2)
    for number in range(3, n, 2):  # only consider odd numbers
        if any(number % prime == 0 for prime in primes):
            continue
        else:
            primes.add(number)
    return len(primes)

def count_primes(n):
    """Sieve of Eratosthenes
    https://www.geeksforgeeks.org/prime-numbers/
    https://labuladong.gitbook.io/algo-en/iv.-high-frequency-interview-problem/print_primenumbers
 
    Time Complexity O(log(logn))

    Other algorithm solving this problem:
       - Segmented Sieve
       - Sieve of Sundaram
       - Bitwise Sieve
    """
    if n < 2:
            return 0
    strikes = [1] * n  # strike list for the input range, initialized at 1
    strikes[0] = 0
    strikes[1] = 0
    for i in range(2, int(n**0.5)+1):
        if strikes[i] != 0:
            strikes[i*i:n:i] = [0] * len(strikes[i*i:n:i])
    return sum(strikes)

def count_primes(n):
    """Sieve of Eratosthenes with optimizations"""
    if n < 3:
        return 0
    sieve = [1] * (n-2)
    for t in range(2, ceil(sqrt(n))):
        if sieve[t-2] == 1:
            sq = t**2
            sieve[sq-2 : n : t] = [0] * ((n-1)//t - t + 1)

    return sum(sieve)