In this tutorial, I will show you how to check if a number is a prime number in Python using 4 different algorithms from easy to advanced.
Table of Contents
- Check Prime Number by Counting Divisors in Python
- Check Prime Number by Checking Divisors in Python
- Check Prime Number by Checking Divisors in Python (Optimized)
- Check Prime Number using the Sieve of Eratosthenes in Python
The naive solution to check if a number is a prime number is to count the number of divisors.
First, let's remind of the definition of a prime number. Prime numbers are numbers:
- greater than 1
- divisible by 1 and itself only, in other words, it has exactly two divisors.
For example, 2, 3, 5, 7, 11, etc. are prime numbers.
Based on this observation, we can write a naive algorithm to check if it has exactly two divisors or not.
The naive solution is not efficient as we have to check all the numbers from 1 to n and count the number of divisors.
Going back to the definition of a prime number, we can see that it is divisible by 1 and itself only.
So, the better solution is to try to check if it is divisible by any number from 2 to n - 1. If so, it is not a prime number.
Cool, we eliminated the divisor count variable. But it can still be improved.
We will optimize the above solution by reducing the number of iterations.
In other words, we will only check if it is divisible by any number from 2 to
nis a composite number, then it can be written as
n = a * bwhere
bare integers greater than 1.
a > sqrt(n)and
b > sqrt(n), then
a * b > n, which is a contradiction because
a * b = n.
- So, at least one of
bmust be less than or equal to
- That means if
nis a composite number, then it must have a prime factor less than or equal to
Based on this, the optimized solution is to check if it is divisible by any number from 2 to sqrt(n).
Cool, the number of iterations is reduced to
Let's continue with an advanced algorithm to check if a number is a prime number in Python called the Sieve of Eratosthenes.
The Sieve of Eratosthenes is an algorithm that can precompute all the prime numbers from 1 to n in
O(n * log(log(n))) time complexity.
So, the next time someone give you a bunch of
m questions asking you to check if a number is a prime number, you can answer each question in
O(1) time complexity.
In general, the Sieve of Eratosthenes is an algorithm that filters out all the composite numbers from 1 to
n, giving us all the prime numbers from 1 to
n. See the visualization below.
Look at the matrix below and help me to do this:
- Click on the multiples of 2, except 2: 4, 6, 8, etc.
- Click on the multiples of 3, except 3: 6, 9, 12, etc.
- Click on the multiples of 5, except 5: 10, 15, 20, etc.
- Click on the multiples of 7, except 7: 49, 77, 91, etc.
- Click on 1.
- Now, watch the visualization carefully.
You can play again here.
As you can see, it filters out the numbers you clicked, and the remaining numbers are prime numbers from 1 to 100. That's basically how the Sieve of Eratosthenes works.
I have made the visualizer for the Sieve of Eratosthenes algorithm. Now let's turn it into a explicit algorithm.
Now that the
is_prime array will be an array of boolean values, where
i is a prime number, and
Okay cool, we have learned how to check if a number is a prime number in Python with 4 solutions:
- The Naive Solution, expensive but easy to understand
- The Better Solution, better but still expensive
- The Better++ Solution, optimal for most cases
- The Sieve of Eratosthenes, optimal for a large number of queries