## Writing C in Python with Cython¶

### Implementing the Eratosthenes Sieve in Python and Cython¶

In :
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 :
primes_python(20)

Out:
[2, 3, 5, 7, 11, 13, 17, 19]
In :
n = 10000

In :
%timeit primes_python(n)

Out:
100 loops, best of 3: 4 ms per loop
In :
%load_ext Cython

In :
%%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 :
primes_cython_1(20)

Out:
[2, 3, 5, 7, 11, 13, 17, 19]
In :
%timeit primes_cython_1(n)

Out:
100 loops, best of 3: 1.99 ms per loop
In :
%%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 :
%timeit primes_cython_2(n)

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