Checking if a number is prime in Python

A pretty simple and concise brute-force solution to check whether a number N is prime: simply check if there is any divisor of N from 2 up to the square root of N (see why here if interested).

The following code is compatible with both Python 2 and Python 3:

from math import sqrt
from itertools import count, islice

def is_prime(n):
    return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n) - 1)))

And here’s a simpler Python 3 only implementation:

def is_prime(n):
    return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1))

Here are the extended versions of the above for clarity:

from math import sqrt
from itertools import count, islice

def is_prime(n):
    if n < 2:
        return False

    for divisor in islice(count(2), int(sqrt(n) - 1)):
        if n % divisor == 0:
            return False

    return True

def is_prime(n):
    if n < 2:
        return False

    for divisor in range(2, int(n ** 0.5) + 1):
        if n % divisor == 0:
            return False

    return True

This is not meant to be anything near the fastest nor the most optimal primality check algorithm, it only accomplishes the goal of being simple and concise, which also reduces implementation errors. It has a time complexity of O(sqrt(n)).

If you are looking for faster algorithms to check whether a number is prime, you might be interested in the following:

• Finding primes & proving primality: brief overview and explanation of the most famous primality tests and their history.
• Probabilistic primality tests (Wikipedia): these can be incorporated in the above code rather easily to skip the brute force if they do not pass, as an example there is this excellent answer to the duplicate of this question.
• Fast deterministic primaliry tests (Wikipedia)
• This Q&A Fastest way to list all primes below N along with the pyprimesieve library.

---

Implementation notes

You might have noticed that in the Python 2 compatible implementation I am using itertools.count() in combination with itertools.islice() instead of a simple range() or xrange() (the old Python 2 generator range, which in Python 3 is the default). This is because in CPython 2 xrange(N) for some N such that N > 2⁶³ ‒ 1 (or N > 2³¹ ‒ 1 depending on the implementation) raises an OverflowError. This is an unfortunate CPython implementation detail.

We can use itertools to overcome this issue. Since we are counting up from 2 to infinity using itertools.count(2), we’ll reach sqrt(n) after sqrt(n) - 1 steps, and we can limit the generator using itertools.islice().