Python Programs to Check Prime Number

A Prime Number is a number that can only be divided by itself and 1 without remainders (e.g., 2, 3, 5, 7, 11).

In this article, we’ll dive into how to write a Python program to determine whether a given number is prime. This is a classic programming exercise that helps solidify your understanding of loops, conditional statements, and basic mathematical concepts.

This article explores several ways to check if a number is prime. Let’s see each one by one.

1. How to Check if Number is Prime In Python

Code Example:

def is_prime(n):
    if n <= 1:
        return False  # Numbers <= 1 are not prime

    # Loop through numbers from 2 to n-1
    for i in range(2, n):
        if n % i == 0:  # Check divisibility
            return False

    # if no divisor found then its a Prime Number
    return True


print(is_prime(19))     # True
print(is_prime(49))     # FalseCode language: Python (python)

2. Using math.sqrt function

In this section, we’ll use Python math module to check if number is Prime number.

The math.sqrt() function in is used to calculate the square root of a given number. By calculating the square root of the given number we only need to check for divisors up to the square root of the number. This significantly improves efficiency.

This method significantly improves efficiency compared to the basic method discussed above, especially for larger numbers, by reducing the number of iterations to roughly half of n.

For instance, consider n = 49:

• The square root of 49 is 7.
• The loop iterates only through numbers 2 to 7, skipping checks for 8 through 48.
• When it finds 49 % 7 == 0, confirming that 49 is not a prime number.

Code Example:

import math

n = 19
is_prime = True

if n <= 1:
    is_prime = False # Numbers <= 1 are not prime

# Check divisors up to the square root of n
for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
        is_prime = False

print(f"Is {n} a prime number? - {is_prime}")


# Output:
# Is 19 a prime number? - TrueCode language: Python (python)

Explanation:

• Edge case: Numbers less than or equal to 1 are immediately classified as not prime because prime numbers are greater than 1.
• Use of math.sqrt: The math.sqrt function calculates the square root of n.
• For Loop: The loop iterates from 2 up to and including √n, significantly reducing the number of checks needed compared to iterating through all numbers up to n-1.
• Modulo operator (%): The modulo operator is used to check divisibility. If n % i == 0, then i is a divisor of n, indicating that the number is not prime.

3. Optimized Method (Skipping Even Numbers)

This method skips even numbers (other than 2) to optimize the process by reducing unnecessary checks. 

Even numbers greater than 2 are always divisible by 2, so they can never be prime. By skipping these numbers, the loop only needs to check odd numbers. This method offers a significant performance improvement by combining the exclusion of even numbers and limiting checks to √n, making it suitable for larger inputs.

Code Example:

import math

n = 19
is_prime = True

# Handle special cases for 1 and 2
if n <= 1:
    is_prime = False
elif n == 2:
    is_prime = True  # 2 is the only even prime number
elif n % 2 == 0:
    is_prime = False

# Loop through odd numbers from 3 to √n
sqrt_number = int(math.sqrt(number)) + 1  # Add 1 to ensure we check the square root itself
for i in range(3, sqrt_number, 2):
    if n % i == 0:
        is_prime = False

print(f"Is {n} a prime number? - {is_prime}")

# Output:
# Is 19 a prime number? - TrueCode language: Python (python)

Explanation:

• Edge cases: Handles exceptional cases explicitly:
  • Numbers less than or equal to 1 are not prime as they do not satisfy the definition of a prime number.
  • The number 2 is treated as a special case because it is the only even prime number.
• Even number check: Eliminates all even numbers greater than 2 by checking if n % 2 == 0. This step skips half of the potential divisors, significantly reducing unnecessary computations.
• Loop: Iterates only through odd numbers starting from 3 up to √n, skipping all even numbers to optimize performance further. By stepping through odd numbers using range(3, int(math.sqrt(n)) + 1, 2).

4. Using the all() function with List Comprehension

The all() function is a Python’s built-in function that returns True if all conditions in an iterable evaluate to True. List comprehension is a concise syntax to construct lists or generators, and here, it is used to create a range of numbers to check divisibility of n.

This combination ensures an efficient and compact way to test primality. Here, we are using all the methods discussed above but in a concise way.

Code Example:

import math

n = 19
is_prime = True
if n <= 1:
    is_prime = False  # Numbers less than or equal to 1 are not prime
is_prime = all(n % i != 0 for i in range(2, int(math.sqrt(n)) + 1))
print(f"Is {n} a prime number? - {is_prime}")

# Output:
# Is 19 a prime number? - TrueCode language: Python (python)

Explanation:

• Edge case: The algorithm begins by checking if n > 1, as prime numbers must be greater than 1.
• all() function: This Python built-in function returns True only if all conditions in an iterable are True. In this example, it checks that n is not divisible by any number in the range from 2 to √n. If any divisor is found (where n % i == 0), all() stops further checks and returns False, making the process efficient.
• List comprehension: The range of divisors is generated using list comprehension. Instead of creating an actual list, it uses a generator expression to test divisibility, which is memory-efficient since no intermediate list is stored. This ensures concise and readable code while maintaining performance.
• Efficiency: The combination of all() and a generator expression allows the program to short-circuit as soon as a divisor is found, avoiding unnecessary computations and improving speed for larger numbers.

Summary

Each method offers a balance of simplicity, efficiency, and readability, depending on the specific use case. For large inputs, the optimized methods are recommended.

• Basic Method:
  • Advantage: Simple to understand and implement.
  • Time Complexity: O(n) – Slow. Iterates through all numbers from 2 to n-1.
  • Space Complexity: O(1) – Requires minimal space as only a few variables are used.
• Using math.sqrt function: Time efficient Method
  • Advantage: Efficient for large numbers by reducing the number of iterations.
  • Time Complexity: O(√n) – Iterates up to the square root of n.
  • Space Complexity: O(1) – Uses a constant amount of space for variables.
• Skipping Even Numbers: Time efficient Method
  • Advantage: Further reduces iterations by skipping all even numbers except 2.
  • Time Complexity: O(√n) – Similar to the √n method but with fewer iterations due to skipping even numbers.
  • Space Complexity: O(1) – Minimal additional memory usage.
• all() with List Comprehension: Time efficient Method, code optimization
  • Advantage: Concise and Pythonic implementation, suitable for compact and readable code.
  • Time Complexity: O(√n) – Checks divisibility only up to √n.
  • Space Complexity: O(1) – Uses a generator expression that avoids creating an intermediate list.