Home//

Python Check Prime Number in 4 Ways

Python Check Prime Number in 4 Ways

By Minh Vu

Updated Dec 06, 2023

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.

Check Prime Number by Counting Divisors 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.

check-prime-number-naive.py
``````def is_prime(n):
if n <= 1:
return False

divisor_count = 0

for i in range(1, n + 1):
if n % i == 0:
divisor_count += 1

return divisor_count == 2

print(is_prime(2)) # True
print(is_prime(3)) # True
print(is_prime(4)) # False
print(is_prime(5)) # True
``````

Check Prime Number by Checking Divisors in Python

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.

check-prime-number-better.py
``````def is_prime(n):
if n <= 1:
return False

for i in range(2, n):
if n % i == 0:
return False

return True
``````

Cool, we eliminated the divisor count variable. But it can still be improved.

Check Prime Number by Checking Divisors in Python (Optimized)

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 `sqrt(n)`.

• Suppose `n` is a composite number, then it can be written as `n = a * b` where `a` and `b` are integers greater than 1.
• If `a > sqrt(n)` and `b > sqrt(n)`, then `a * b > n`, which is a contradiction because `a * b = n`.
• So, at least one of `a` and `b` must be less than or equal to `sqrt(n)`.
• That means if `n` is a composite number, then it must have a prime factor less than or equal to `sqrt(n)`.

Based on this, the optimized solution is to check if it is divisible by any number from 2 to sqrt(n).

check-prime-number-better-plus.py
``````def is_prime(n):
if n <= 1:
return False

for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False

return True
``````

Cool, the number of iterations is reduced to `sqrt(n)`.

Check Prime Number using the Sieve of Eratosthenes in Python

Let's continue with an advanced algorithm to check if a number is a prime number in Python called the Sieve of Eratosthenes.

What is 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.

How does the Sieve of Eratosthenes work?

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.
The Sieve of Eratosthenes Visualization

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.

Implementation of the Sieve of Eratosthenes in Python

check-prime-number-sieve-of-eratosthenes.py
``````def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False

return is_prime

print(sieve_of_eratosthenes(100))
``````

Result

Now that the `is_prime` array will be an array of boolean values, where `is_prime[i]` is `True` if `i` is a prime number, and `False` otherwise.

check-prime-number-sieve-of-eratosthenes.py
``````print(is_prime[2]) # True
print(is_prime[3]) # True
print(is_prime[4]) # False
print(is_prime[5]) # True
``````

Conclusion

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

Minh Vu

Software Engineer

Hi guys, I'm the author of WiseCode Blog. I mainly work with the Elastic Stack and build AI & Python projects. I also love writing technical articles, hope you guys have good experience reading my blog!

Minh Vu

Software Engineer

Related Posts

See All Posts

Do not find what you need?

Send us a message.