Writing C in Python with Cython

Installing Cython and a C compiler for Python

Implementing the Eratosthenes Sieve in Python and Cython

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