The Python Quants

Checking Prime Characteristic with Python

Dr. Yves J. Hilpisch

The Python Quants GmbH

analytics@pythonquants.com

www.pythonquants.com

Inspired by an example (pp. 221+) in the excellent book High Performance Python ("HPP") from Micha Gorelick and Ian Oszvald (O'Reilly 2014), this IPython Notebook compares several Python-based implementations of algorithms to check whether a given positive integer is a prime or not. The focus lies of sequential algorithms only.

Test Numbers

In [1]:
np = 100109100129101027  # non-prime
In [2]:
p0 = 1e8 + 7 # small prime
In [3]:
p1 = 100109100129100151  # prime 1 from HPP
In [4]:
p2 = 100109100129162907  # prime 2 from HPP

From HPP Book

Pure Python

In [5]:
def check_prime(n):
    if n % 2 == 0:
        return False
    from_i = 3
    to_i = n ** 0.5 + 1
    for i in xrange(from_i, int(to_i), 2):
        if n % i == 0:
            return False
    return True
In [6]:
%time check_prime(np)
CPU times: user 4.45 s, sys: 27 ms, total: 4.48 s
Wall time: 4.37 s

Out[6]:
False
In [7]:
%time check_prime(p0)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 399 µs

Out[7]:
True
In [8]:
%time check_prime(p1)
CPU times: user 8.06 s, sys: 64 ms, total: 8.12 s
Wall time: 7.99 s

Out[8]:
True
In [9]:
%time check_prime(p2)
CPU times: user 8.05 s, sys: 51 ms, total: 8.1 s
Wall time: 7.97 s

Out[9]:
True

Numba Compiled

In [10]:
import numba as nb
In [11]:
cpnb = nb.jit(check_prime)
In [12]:
%timeit cpnb(np)
1 loops, best of 3: 732 ms per loop

In [13]:
%timeit cpnb(p2)
1 loops, best of 3: 1.35 s per loop

Improved Algorithm

Pure Python

In [14]:
def is_prime(n):
    if n % 2 == 0 or n % 3 == 0:
        return False
    limit = int(n ** .5)
    for f in xrange(5, limit, 6):
        if n % f == 0 or n % (f + 2) == 0:
            return False
    return True
In [15]:
%time is_prime(np)
CPU times: user 3.04 s, sys: 38 ms, total: 3.08 s
Wall time: 2.99 s

Out[15]:
False
In [16]:
%time is_prime(p0)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 281 µs

Out[16]:
True
In [17]:
%time is_prime(p1)
CPU times: user 5.6 s, sys: 66 ms, total: 5.66 s
Wall time: 5.52 s

Out[17]:
True
In [18]:
%time is_prime(p2)
CPU times: user 5.56 s, sys: 67 ms, total: 5.62 s
Wall time: 5.49 s

Out[18]:
True

Numba Compiled

In [19]:
ipnb = nb.jit(is_prime)
In [20]:
%timeit ipnb(np)
1 loops, best of 3: 472 ms per loop

In [21]:
%timeit ipnb(p0)
1000 loops, best of 3: 219 µs per loop

In [22]:
%timeit ipnb(p1)
1 loops, best of 3: 871 ms per loop

In [23]:
%timeit ipnb(p2)
1 loops, best of 3: 871 ms per loop

While Algorithm

Pure Python

In [24]:
def is_while(n):
    if n % 2 == 0 or n % 3 == 0:
        return False
    limit = int(n ** .5)
    f = 5
    while f < limit:
        if n % f == 0 or n % (f + 2) == 0:
            return False
        f += 6
    return True
In [25]:
%time is_while(np)
CPU times: user 3.82 s, sys: 38 ms, total: 3.86 s
Wall time: 3.79 s

Out[25]:
False
In [26]:
%time is_while(p2)
CPU times: user 7.08 s, sys: 22 ms, total: 7.1 s
Wall time: 7.05 s

Out[26]:
True

Numba Compiled

In [27]:
iwnb = nb.jit(is_while)
In [28]:
%timeit iwnb(np)
1 loops, best of 3: 479 ms per loop

In [29]:
%timeit iwnb(p2)
1 loops, best of 3: 883 ms per loop

Cython Version

In [30]:
%load_ext cython
In [31]:
%%cython
def ipcy(long n):
    if n % 2 == 0 or n % 3 == 0:
        return False
    cdef int limit, f
    limit = int(n ** .5)
    for f in xrange(5, limit, 6):
        if n % f == 0 or n % (f + 2) == 0:
            return False
    return True
In [32]:
%time ipcy(np)
CPU times: user 474 ms, sys: 0 ns, total: 474 ms
Wall time: 474 ms

Out[32]:
False
In [33]:
%time ipcy(p0)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 37.9 µs

Out[33]:
True
In [34]:
%time ipcy(p1)
CPU times: user 873 ms, sys: 0 ns, total: 873 ms
Wall time: 872 ms

Out[34]:
True
In [35]:
%timeit ipcy(p2)
1 loops, best of 3: 872 ms per loop