In this article we are going to look a some different ways to check whether a number is prime using Python. As well as being an interesting and useful exercise, this exploration also highlights the importance of considering the efficiently of algorithms – depending on our implementation, different algorithms for performing the same task can require dramatically more time or resources. For a detailed look at the efficiency of algorithms, check out this article: Time Complexity in Python Programming.

Computer programming and Mathematics are deeply connected. You can greatly develop your understanding of both subjects by exploring the connections between them.

Before looking at the examples below, it is a good idea to attempt to write your own function is_prime(), which takes an input n and determines whether it is prime or not. Before you do, think of some examples you wish to test, so you know whether you function is behaving how you expect. Don’t worry if you can’t get it right to start with – just having tried will mean that you get a lot more from seeing correct solutions.

For all of the examples below, assume the input n is a positive integer greater than 1. You could enforce this with conditionals or assert statements, but I have chosen to leave it as an assumption to keep the code as clear as possible.

Top tip: to find whether one number divides another exactly (AKA is a factor or divisor of that number), you can use the % operator to see if the remainder of diving them is 0. If this is news to you, you may want to make a detour and learn about the % operator before continuing.

For our purposes, prime number is a positive integer greater than 1 whose only divisors are 1 and itself.

Checking Prime Numbers in Python Version 1

Our first version of a function to check primality uses the brute force approach of running through all the numbers from 2 to n - 1 to see if each is a factor of n. If we find any such factor, then n is not prime, as it can be divided exactly by that factor. The time module is needed to perform our timings to see how long each function takes to run.

import time


def is_prime_1(n):
    """
    Checks whether n is a prime number.
    Uses a brute force search for factors between 1 and n.
    """
    for f in range(2, n):  # Check for factors from 2 to n - 1
        if n % f == 0:  # is n divisible by f?
            print(f"{f} is a factor of {n}.")
            return False
    print(f"{n} is prime.")
    return True


start = time.perf_counter()
is_prime_1(75235273)  # 75235273 is a prime number
end = time.perf_counter()
print(f"Checked all factors from 2 to n - 1. Seconds taken: {end - start:.7f}")

Output:

75235273 is prime.
Checked all factors from 2 to n - 1. Seconds taken: 7.1961917

If you know about time complexity and Big O notation, this algorithm is O(n), or linear, which is not very efficient at all, as you can see from the time taken to determine whether 75235273 is prime.

Not particularly melodic, but here’s a sonic representation of the the first 500 prime numbers.

Checking Prime Numbers in Python Version 2

The next version of our function makes use of the fact that the largest factor of a number besides itself is its square root. Take moment to think about why this is true.

An integer n divided by a number which is greater than its square root will give a value less than its square root.

Here’s a short detour to emphasize this point, using an actual square number to make it clearer:

8 is the square root of 64. if I divide 64 by 9, I get a number less than 8. That is, 7.11 ( to 2 d.p.). It’s like a see-saw with the exact square root in the middle…

This mathematical fact allows us to drastically reduce the number of checks needed before we can conclusively say whether a number is prime or not. The time complexity in the worst case is now O(√n) which is a vast improvement on our previous attempt.

def is_prime_2(n):
    """
    Checks whether n is a prime number.
    Uses a brute force search for factors between 1 and √n.
    """
    max_factor = int(n ** 0.5)
    print(f"Maximum factor < n: {max_factor}")
    for f in range(2, max_factor + 1): # Don't forget the upper bound for `range` is not inclusive.
        if n % f == 0:  # is n divisible by f?
            print(f"{f} is a factor of {n}.")
            return False
    print(f"{n} is prime.")
    return True


start = time.perf_counter()
is_prime_2(75235273)  # 75235273 is a prime number
end = time.perf_counter()
print(f"Checked for factors up to square root of n. Seconds taken: {end - start:.7f}")

Output:

Maximum factor < n: 8673
75235273 is prime.
Checked for factors up to square root of n. Seconds taken: 0.0007206

A very significant improvement indeed!

Checking Prime Numbers in Python Version 3

Our third attempt makes use of the fact that all prime numbers except 2 are odd, so there is no need to check any other even numbers. This allows us to reduce the time complexity further, which although a significant improvement, doesn’t actually change the Big O class, which is still O(√n) in the worst case, since, Big O is not effected by constant multiples.

def is_prime_3(n):
    """
    Checks whether n is a prime number.
    Search for factors between 1 and √n, but only odd numbers past 2.
    """
    max_factor = int(n ** 0.5)
    print(f"Maximum factor < n: {max_factor}")
    if n % 2 == 0:
        print(f"2 is a factor of {n}.")
        return False
    for f in range(3, max_factor + 1, 2):  # Don't forget the upper bound for `range` is not inclusive.
        if n % f == 0:  # is n divisible by f?
            print(f"{f} is a factor of {n}.")
            return False
    print(f"{n} is prime.")
    return True


start = time.perf_counter()
is_prime_3(75235273)  # 75235273 is a prime number
end = time.perf_counter()
print(f"Checked for 2 and odd factors up to square root of n. Seconds taken: {end - start:.7f}")

Output:

Maximum factor < n: 8673
75235273 is prime.
Checked for 2 and odd factors up to square root of n. Seconds taken: 0.0003785

This article has explored some algorithms for testing for primality in Python. There are other approaches which could be used, which make use of interesting facts relating to Number Theory. What we have do here gives a good introduction, and hopefully if you even find you need to implement an algorithm in Python to check for primality, you will be able to do so, and for your algorithm to be at least moderately efficient.

Happy computing!

Sharing is caring!