def primes_python(n):
    primes = [False, False] + [True] * (n - 2)
    i = 2
    while i < n:
        # We do not deal with composite numbers.
        if not primes[i]:
            i += 1
            continue
        k = i * i
        # We mark multiples of i as composite numbers.
        while k < n:
            primes[k] = False
            k += i
        i += 1
    # We return all numbers marked with True.
    return [i for i in range(2, n) if primes[i]]

primes_python(20)

n = 10000

%timeit primes_python(n)

%load_ext Cython

%%cython
def primes_cython_1(n):
    primes = [False, False] + [True] * (n - 2)
    i = 2
    while i < n:
        # We do not deal with composite numbers.
        if not primes[i]:
            i += 1
            continue
        k = i * i
        # We mark multiples of i as composite numbers.
        while k < n:
            primes[k] = False
            k += i
        i += 1
    # We return all numbers marked with True.
    return [i for i in range(2, n) if primes[i]]

primes_cython_1(20)

%timeit primes_cython_1(n)

%%cython -a
def primes_cython_2(int n):
    # Note the type declarations below:
    cdef list primes = [False, False] + [True] * (n - 2)
    cdef int i = 2
    cdef int k = 0
    # The rest of the function is unchanged.
    while i < n:
        # We do not deal with composite numbers.
        if not primes[i]:
            i += 1
            continue
        k = i * i
        # We mark multiples of i as composite numbers.
        while k < n:
            primes[k] = False
            k += i
        i += 1
    # We return all numbers marked with True.
    return [i for i in range(2, n) if primes[i]]

%timeit primes_cython_2(n)