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

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

`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