How to Check if a Number is Prime in Python
This tutorial will teach you how to write a Python program to check if a number is prime or not.
If you’ve ever taken up coding tests, you’ll have come across the math question on the test for primality or to check if a number is prime. And over the next few minutes, you’ll learn to come up with the optimal solution to this question.
In this tutorial, you’ll:
 review the basics of prime numbers,
 write Python code to check if a number is prime, and
 optimize it further to get an O(√n) runtime algorithm.
For all this and more, let’s get started.
What is a Prime Number?
Let’s start by reviewing the basics of prime numbers.
In number theory, a natural number n said to be prime if it has exactly two factors: 1 and the number itself (n). Recall from your school math: a number i is said to be a factor of the number n, if i divides n evenly. ✅
The following table lists down a few numbers, all their factors, and if they’re prime.
n  Factors  Is Prime? 
1  1  No 
2  1, 2  Yes 
3  1, 3  Yes 
4  1, 2, 4  No 
7  1, 7  Yes 
15  1, 3, 5, 15  No 
From the above table, we can write down the following:
 2 is the smallest prime number.
 1 is a factor of every number.
 Every number
n
is a factor of itself.
So 1 and n are trivial factors for any number n. And a prime number should not have any factors other than these two.
This means that when you go from 2 to n – 1, you should not be able to find a nontrivial factor that divides n without a remainder.
O(n) Algorithm to Check if a Number is Prime in Python
In this section, let us formalize the above approach into a Python function.
You can loop through all numbers from 2 to n – 1 using the range()
object in Python.
In Python,
range(start, stop, step)
returns a range object. You can then iterate over the range object to get a sequence fromstart
all the way up tostop 1
in steps ofstep
.
Since we need the set of integers from 2 to n1, we can specify range(2, n)
and use it in conjunction with for
loop.
Here’s what we would like to do:
 If you find a number that divides n evenly without a remainder, you can immediately conclude that the number is not prime.
 If you’ve looped through the entire range of numbers from 2 all the way up to n – 1 without finding a number that divides n evenly, then the number is prime.
Python Function to Check for Prime Number
Using the above, we can go ahead and define the function is_prime()
as follows.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Let’s now parse the above function definition.
 The above function
is_prime()
takes in a positive integer n as the argument.  If you find a factor in the specified range of (2, n1), the function returns
False
—as the number is not prime.  And it returns
True
if you traverse the entire loop without finding a factor.
Next, let’s call the function with arguments and verify if the output is correct.
is_prime(2)
# True
is_prime(8)
# False
is_prime(9)
# False
is_prime(11)
# True
In the output above, you see that 2 and 11 are prime (the function returns True
). And 8 and 9 are not prime (the function returns False
).
How to Optimize the Python Function is_prime()
We can do a small optimization here. Observe the list of factors in the table below.
Number  Factors 
6  1, 2, 3, 6 
10  1, 2, 5, 10 
18  1, 2, 3, 6, 9, 18 
Well, we can see that the only factor of n that is greater than n/2 is n itself.
So this means you don’t have to loop all the way up to n – 1. You can instead run the loop only up to n/2.
If you don’t find a nontrivial factor till n/2, you can’t find one beyond n/2 either.
Now let’s modify the function is_prime()
to check for factors in the range (2, n/2)
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Let’s go ahead and verify the output through a few function calls.
is_prime(9)
# False
is_prime(11)
# True
Even though it may seem like we have optimized, this algorithm is not more efficient than the previous one in terms of runtime complexity. In fact, both of them have O(n) runtime complexity: proportional to the value of n or linear in n.
Can we do better? Yes, we can!
▶️ Proceed to the next section to determine how to improve the time complexity for prime number testing.
O(√n) Algorithm to Check for Prime Number in Python
It happens that the factors of a number occur in pairs.
If a is a factor of the number n, then there also exists a factor b such that a x b = n, or simply, ab = n.
Let’s verify this through an example.
The table below shows the factors of the number 18 occurring in pairs. You may verify the same for a few more numbers if you like.
Also, note that √18 is approximately 4.24.
And in the factors that occur in pairs (a, b), you can see that if a is less than 4.24, then b is greater than 4.24—in this example, (2, 18) and (3, 6).
a  b 
1  18 
2  9 
3  6 
The figure below shows the factors of 18 plotted on the number line.
If the number n happens to be a perfect square, you’ll have a = b = √n as one of the factors.
▶️ Look at the factors of 36 in the table below. As 36 is a perfect square, a = b = 6 is one of the factors. For all other factor pairs (a, b), a < 6 and b > 6 holds.
a  b 
1  36 
2  18 
3  12 
4  9 
6  6 
Summing up, we have the following:
 Every number n can be written as n = a x b
 If n is a perfect square, then a = b = √n.
 And if a < b, then, a < √n and b > √n.
 Else, if a > b, then a > √n and b < √n.
So instead of looping through all integers up to n/2, you may choose to run up to √n. And this is a lot more efficient than our previous approach.
How to Modify is_prime() to O(√n) Algorithm
Let’s proceed to optimize the function to check for prime numbers in Python.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Now, let’s parse the above function definition:
 To compute the square root of a number, let’s import Python’s builtin math module, and use
math.sqrt()
function.  As n may not be a perfect square, we’ll have to cast it into an integer. Use
int(var)
to castvar
into anint
.  To make sure we’re actually checking up to √n, we add a plus one as the
range()
function excludes the endpoint of the range by default.
The code cell below verifies that our function is_prime()
works correctly.
is_prime(8)
# False
is_prime(15)
# False
is_prime(23)
# True
In the next section, let us create a few simple plots to understand O(n) and O(√n) visually.
Comparing O(n) and O(√n) Visually
▶️ Run the following code snippet in a Jupyter notebook environment of your choice.
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
The above snippet shows how you can plot the curves for n and √n for a range of values.
 We use the NumPy arange() function to create an array of numbers.
 And then, we collect the values of n and √n up to, but not including 20, into a pandas DataFrame.
 Next, we plot using seaborn’s lineplot() function.
From the plot below, we see that √n is significantly smaller than n.
Let us now increase the range to as high as 2000 and repeat the same steps as above.
import numpy as np
import seaborn as sns
import pandas as pd
n = 2000
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
From the above plot, you can infer that O(√n) algorithm is significantly faster when you’re testing if a large number is prime.
Here’s a quick example: 2377 is a prime number—verify this!😀
While the O(n) approach will take the order of 2000 steps, the O(√n) algorithm can help arrive at the answer in just 49 steps.✅
Conclusion
⏳ And it’s time for a quick summary.
 To check if a number is prime, the naïve approach is to loop through all numbers in the range (2, n1). If you don’t find a factor that divides n, then n is prime.
 As the only factor of n greater than n/2 is n itself, you may choose to run only up to n/2.
 Both of the above approaches have a time complexity of O(n).
 As factors of a number occur in pairs, you can run only up to √n. This algorithm is a lot faster than O(n). And the gain is appreciable when checking if a large number is prime or not.
I hope you understand how to check if a number is prime in Python. As a next step, you may check out our tutorial on Python programs on string operations—where you’ll learn to check if strings are palindromes, anagrams, and more.
See you all in another tutorial. Until then, happy coding!👩🏽💻
 Tagged in:
 Python
More great readings on Development

How to Install Anaconda on LinuxAnesu Kafesu on September 29, 2022

12 Top Search Solutions for Ecommerce and Big SitesAmrita Pathak on September 27, 2022

11 InApp Chat Solutions to Build Better User EngagementTamal Das on September 22, 2022

Difference Between Bug, Defect, Error, Failure, and Fault in Software TestingAmrita Pathak on September 22, 2022

How to Install Yarn on Windows?Bipasha Nath on September 21, 2022

21 Frequently Asked OOP Interview Questions and Answers to Know TodayDurga Prasad Acharya on September 27, 2022
The more you learn, the better you become.
Every week we share trending articles and tools in our newsletter. More than 10,000 people enjoy reading, and you will love it too.