Checking if a number is a prime number in Python [duplicate]

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 sqrtfrom itertools import count, islicedef 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 sqrtfrom itertools import count, islicedef 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().

There are many efficient ways to test primality (and this isn't one of them), but the loop you wrote can be concisely rewritten in Python:

def is_prime(a):    return all(a % i for i in xrange(2, a))

That is, a is prime if all numbers between 2 and a (not inclusive) give non-zero remainder when divided into a.

This is the most efficient way to see if a number is prime, if you only have a few queries. If you ask a lot of numbers if they are prime, try Sieve of Eratosthenes.

import mathdef is_prime(n):    if n == 2:        return True    if n % 2 == 0 or n <= 1:        return False    sqr = int(math.sqrt(n)) + 1    for divisor in range(3, sqr, 2):        if n % divisor == 0:            return False    return True