How to Check if a Number Is Prime in Python

Vaibhhav Khetarpal Feb 02, 2024
  1. Use the Simple Iteration Method to Determine a Prime Number in Python
  2. More Optimized Approach of the Simple Iteration Method to Determine a Prime Number in Python
  3. Use the sympy.isprime() Function to Check if the Given Number Is a Prime Number in Python
  4. Use the Sieve of Eratosthenes to Check if the Given Number Is a Prime Number in Python
  5. Conclusion
How to Check if a Number Is Prime in Python

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:

  • Start by defining a function named is_prime_simple_iteration that takes a single argument num – the number to be checked for primality.
  • 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.

  • Begin by defining a new function named is_prime_optimized that takes a single argument num.
  • 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.

  • Start by defining a function named sieve_of_eratosthenes that takes a single argument limit – the upper limit for generating prime numbers.
  • 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[0] = primes[1] = 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[0] = primes[1] = 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 Khetarpal avatar Vaibhhav Khetarpal avatar

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.

LinkedIn