In [1]:

    

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]]


    

In [2]:

    

primes_python(20)


    

    
Out[2]:





[2, 3, 5, 7, 11, 13, 17, 19]

In [3]:

    

n = 10000


    

In [4]:

    

%timeit primes_python(n)


    

    
Out[4]:





100 loops, best of 3: 4 ms per loop

In [5]:

    

%load_ext Cython


    

In [6]:

    

%%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]]


    

In [7]:

    

primes_cython_1(20)


    

    
Out[7]:





[2, 3, 5, 7, 11, 13, 17, 19]

In [8]:

    

%timeit primes_cython_1(n)


    

    
Out[8]:





100 loops, best of 3: 1.99 ms per loop

In [9]:

    

%%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]]


    

In [10]:

    

%timeit primes_cython_2(n)


    

    
Out[10]:





1000 loops, best of 3: 266 µs per loop