Python Check Prime Number in 4 Ways

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.

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
  • What is the Sieve of Eratosthenes?
  • How does the Sieve of Eratosthenes work?
  • Implementation of the Sieve of Eratosthenes in Python
  • Result
• Conclusion

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.

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.

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).

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.

You can try with the Sieve of Eratosthenes Visualizer App.

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

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.

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