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)
[2, 3, 5, 7, 11, 13, 17, 19]
n = 10000
%timeit primes_python(n)
100 loops, best of 3: 4 ms per loop
%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)
[2, 3, 5, 7, 11, 13, 17, 19]
%timeit primes_cython_1(n)
100 loops, best of 3: 1.99 ms per loop
%%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)
1000 loops, best of 3: 266 µs per loop