Checking if a number is a prime number in Python

Question

This question already has answers here:

Answer 1

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

Here's an extended version for clarity:

from math import sqrt
from itertools import count, islice

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

    for number in islice(count(2), int(sqrt(n) - 1)):
        if n % number == 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 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().