## Writing C in Python with Cython¶

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