# Check if a Number Is Prime in Python

Vaibhhav Khetarpal Nov 22, 2023

Understanding and identifying prime numbers is a fundamental aspect of number theory, with applications spanning cryptography, computer science, and various mathematical disciplines. This article explores different methods in Python for determining whether a given number is prime.

Beginning with a simple iteration method, we delve into an optimized version, leverage the `sympy` library’s efficient `isprime()` function, and explore the classical Sieve of Eratosthenes algorithm. Each method is presented with clear step-by-step implementations and practical examples to make it easy to understand.

## Use the Simple Iteration Method to Determine a Prime Number in Python

Before we dive into the implementation, let’s quickly review the characteristics of prime numbers. Prime numbers are fundamental in number theory and have applications in various areas, including cryptography and computer science.

A prime number has exactly two distinct positive divisors: 1 and the number itself.

Here are the steps to implement this iteration method:

• ##### Handle the special case where the given number is less than `2`. By definition, numbers less than `2` are not prime.
``````if num < 2:
return False
``````
• ##### Set up a `for` loop to iterate over potential divisors, starting from `2` up to the square root of the given number. The `int(num**0.5) + 1` ensures that we cover all possible divisors.
``````for i in range(2, int(num**0.5) + 1):
``````
• ##### Inside the loop, check if the given number is divisible by the current divisor (`i`). If it is, return `False` immediately, indicating that the number is not prime.
``````for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
``````
• ##### If the loop completes without finding any divisors, it means the number is prime. Return `True` to indicate primality.

The simple iteration method involves checking for the divisibility of the given number by all integers from `2` to the square root of the number.

If the number is divisible by any of these integers, it is not prime. Otherwise, it is considered prime.

Let’s have an example:

``````def is_prime_simple_iteration(num):
if num < 2:
return False

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

return True

numbers_to_check = [17, 25, 7, 100, 13]

for num in numbers_to_check:
if is_prime_simple_iteration(num):
print(f"{num} is a prime number.")
else:
print(f"{num} is not a prime number.")
``````

Output:

``````17 is a prime number.
25 is not a prime number.
7 is a prime number.
100 is not a prime number.
13 is a prime number.
``````

While this simple iteration method is straightforward, it may not be the most efficient for large numbers. Approximately, its time complexity is `O(√n)`, where `n` is the given number.

For larger primes, more sophisticated algorithms like the Sieve of Eratosthenes or probabilistic methods might be more suitable.

## More Optimized Approach of the Simple Iteration Method to Determine a Prime Number in Python

While the simple iteration method is effective, it can be optimized further by reducing the number of iterations. Instead of checking divisibility by all integers up to the square root, we can focus on specific values.

One common optimization is to check only odd numbers (except for `2`) as potential divisors, as even numbers greater than `2` are not prime.

• ##### Similar to the simple iteration method, handle special cases where the number is less than `2`, equal to `2` (the only even prime), or an even number greater than `2`.
``````def is_prime_optimized(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False  # Even numbers greater than 2 are not prime
``````
• ##### Set up a `for` loop to iterate over odd potential divisors, starting from `3` and incrementing by `2` in each step. This avoids checking divisibility by even numbers.
``````for i in range(3, int(num**0.5) + 1, 2):
``````
• ##### Inside the loop, check if the given number is divisible by the current odd divisor (`i`). If it is, return `False` immediately.
``````if num % i == 0:
return False
``````
• ##### If the loop completes without finding any divisors, it means the number is prime. Return `True` to indicate primality.

Let’s utilize the optimized function to check whether numbers are prime or not.

``````def is_prime_optimized(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False

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

return True

numbers_to_check = [17, 25, 7, 100, 13]

for num in numbers_to_check:
if is_prime_optimized(num):
print(f"{num} is a prime number.")
else:
print(f"{num} is not a prime number.")
``````

Output:

``````17 is a prime number.
25 is not a prime number.
7 is a prime number.
100 is not a prime number.
13 is a prime number.
``````

The optimized approach reduces the number of iterations by excluding even potential divisors, making it more efficient than the simple iteration method. The time complexity remains approximately `O(√n)`, but the constant factor is smaller due to fewer iterations.

## Use the `sympy.isprime()` Function to Check if the Given Number Is a Prime Number in Python

The `sympy` library is a powerful Python library for symbolic mathematics. It includes a variety of functions for number theory, algebra, and calculus.

One such function is `isprime()`, which is designed specifically for determining whether a given number is a prime number. It returns `True` if the number to be verified is prime and `False` if the number is not prime.

The implementation using `sympy.isprime()` is straightforward. First, you need to install the `sympy` library if you haven’t already:

``````pip install sympy
``````

Now, you can use the `isprime()` function in your Python code:

``````from sympy import isprime

number_to_check = 37

if isprime(number_to_check):
print(f"{number_to_check} is a prime number.")
else:
print(f"{number_to_check} is not a prime number.")
``````

Output:

``````37 is a prime number.
``````

Let’s check the primality of a few numbers using `sympy.isprime()`:

``````from sympy import isprime

numbers_to_check = [17, 25, 7, 100, 13]

for num in numbers_to_check:
if isprime(num):
print(f"{num} is a prime number.")
else:
print(f"{num} is not a prime number.")
``````

Output:

``````17 is a prime number.
25 is not a prime number.
7 is a prime number.
100 is not a prime number.
13 is a prime number.
``````

The `sympy.isprime()` function is highly optimized and efficient, making it suitable for various scenarios. It employs a combination of algorithms, including trial division and probabilistic methods, to quickly determine the primality of a number.

This makes it particularly useful when dealing with both small and large numbers.

## Use the Sieve of Eratosthenes to Check if the Given Number Is a Prime Number in Python

The Sieve of Eratosthenes is a classical algorithm devised by the ancient Greek mathematician Eratosthenes to find all prime numbers up to a given limit. The algorithm works by iteratively marking the multiples of each prime, starting from `2` and continuing until the square root of the limit.

By generating a list of primes up to the square root of the number in question, we can then verify its primality efficiently.

• ##### Create a list called `primes` with `True` values initially for all numbers up to the given limit. Set the first two elements (`0` and `1`) to `False` since they are not prime.
``````primes = [True] * (limit + 1)
primes = primes = False
``````
• ##### Set up a `for` loop to iterate over potential primes, starting from `2` and continuing until the square root of the limit.
``````for i in range(2, int(limit**0.5) + 1):
``````
• ##### Inside the loop, check if the current number is marked as a prime. If it is, mark all multiples of the current prime as non-prime.
``````if primes[i]:
for j in range(i * i, limit + 1, i):
primes[j] = False
``````
• ##### Finally, create a list comprehension to generate a list of primes up to the given limit based on the `primes` list.
``````return [x for x in range(limit + 1) if primes[x]]
``````
• ##### Define a function named `is_prime_sieve` that takes a single argument `num` and checks whether it is prime by utilizing the previously generated list of primes.
``````def is_prime_sieve(num):
if num < 2:
return False
return num in sieve_of_eratosthenes(num)
``````

Let’s check the primality of a few numbers using the Sieve of Eratosthenes:

``````def sieve_of_eratosthenes(limit):
primes = [True] * (limit + 1)
primes = primes = False

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

return [x for x in range(limit + 1) if primes[x]]

def is_prime_sieve(num):
if num < 2:
return False
return num in sieve_of_eratosthenes(num)

# Example usage:
numbers_to_check = [17, 25, 7, 100, 13]

for num in numbers_to_check:
if is_prime_sieve(num):
print(f"{num} is a prime number.")
else:
print(f"{num} is not a prime number.")
``````

Output:

``````17 is a prime number.
25 is not a prime number.
7 is a prime number.
100 is not a prime number.
13 is a prime number.
``````

The Sieve of Eratosthenes is highly efficient for generating prime numbers, and adapting it for prime checking provides a constant time operation once the list of primes is generated. However, the initial generation of primes up to the square root of the number can be computationally expensive for large numbers.

## Conclusion

This article has provided a comprehensive overview of diverse techniques to check the primality of numbers in Python.

From the straightforward yet effective simple iteration to an optimized version reducing unnecessary computations and the use of specialized functions like `sympy.isprime()` and the classical Sieve of Eratosthenes, you now have a versatile toolkit for prime number checking.

The choice of method will depend on your specific requirements and the scale of the numbers involved, allowing for flexibility in addressing a wide range of computational challenges related to prime numbers.

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.