7 Different Methods to Check Prime Numbers in Python

Prime numbers are fascinating! They are natural numbers greater than 1 that can't be divided by anything other than 1 and themselves. These unique numbers play a vital role in math and are especially important in fields like computer science and cryptography.

Learning to identify prime numbers is more than just a classroom exercise; it has practical uses in our daily lives. Prime numbers help secure online communications through encryption, improve search algorithms, and even generate random numbers for simulations.

If you're interested in programming, Python makes it easy to check whether a number is prime. You can use simple loops or advanced library functions like `sympy.isprime()`. With all the tools and methods available in Python, both beginners and seasoned pros can tackle primality tests with ease.

In this article, we’ll explore different techniques for checking prime numbers in Python, complete with practical examples, performance insights, and real-world applications. Let’s dive in and discover the world of prime numbers together!

“Enhance your Python skills further with our Data Science and Machine Learning courses from top universities — take the next step in your learning journey!”

Methods to Check Prime Numbers in Python

1. Python Program to Check Prime Number Using for-else statement

def is_prime(number):
    """
    Check if a given number is prime using for-else statement.
    
    Args:
        number (int): The number to be checked for primality.
    
    Returns:
        bool: True if the number is prime, False otherwise.
    """
    # Handle special cases
    if number < 2:
        return False
    
    # Check for divisibility from 2 to the square root of the number
    for divisor in range(2, int(number**0.5) + 1):
        # If number is divisible by any divisor, it's not prime
        if number % divisor == 0:
            return False
    else:
        # This block executes only if no divisors are found
        return True

# Test the function with different numbers
test_numbers = [2, 3, 4, 5, 7, 11, 12, 17, 20, 29]

print("Prime Number Checker Results:")
for num in test_numbers:
    result = is_prime(num)
    print(f"{num} is {'prime' if result else 'not prime'}")

Output

Prime Number Checker Results:
2 is prime
3 is prime
4 is not prime
5 is prime
7 is prime
11 is prime
12 is not prime
17 is prime
20 is not prime
29 is prime

Explanation of Code

1. Function Definition:
2. • We define is_prime() that takes a number as input
   • Handles special cases like numbers less than 2
   • Uses a for loop to check divisibility
2. Prime Checking Logic:
3. • Checks divisibility from 2 to the square root of the number
   • The else block of the for loop is key - it only runs if NO divisors are found
   • Returns True if no divisors are found, indicating a prime number
3. Optimization:
4. • We only check up to the square root of the number to improve efficiency
   • This reduces unnecessary iterations

Key Points About the For-Else Mechanism

• The else block executes only if the for loop completes without encountering a break
• In our prime number check, this means no divisors were found
• This provides a clean, Pythonic way to check primality

Related Reads:

• Python if-else statement
• Conditional Statement in Python

2. Program to Check Prime Number in Python Using Flag Variable

def is_prime(number):
    # Check if the number is less than 2
    # Numbers less than 2 are not prime
    if number < 2:
        return False
    
    # Initialize the flag as True
    # We assume the number is prime until proven otherwise
    is_prime_flag = True
    
    # Check for divisors from 2 to the square root of the number
    # We only need to check up to square root for efficiency
    for i in range(2, int(number**0.5) + 1):
        # If the number is divisible by any value, it's not prime
        if number % i == 0:
            # Set the flag to False
            is_prime_flag = False
            # Exit the loop as soon as a divisor is found
            break
    
    # Return the final state of the flag
    return is_prime_flag

# Test the function with different numbers
test_numbers = [2, 3, 4, 5, 7, 10, 11, 13, 17, 20]

# Print primality of each number
for num in test_numbers:
    print(f"{num} is {'prime' if is_prime(num) else 'not prime'}")

Output

2 is prime
3 is prime
4 is not prime
5 is prime
7 is prime
10 is not prime
11 is prime
13 is prime
17 is prime
20 is not prime

Explanation of Code

Initial Check

• First, we check if the number is less than 2
• Numbers less than 2 are not considered prime
• If the number is less than 2, we immediately return False

Flag Initialization

• We start by setting is_prime_flag to True
• This assumes the number is prime until proven otherwise

Divisibility Check

• We iterate from 2 to the square root of the number
• We only need to check up to the square root for efficiency
• If any number divides the input number without a remainder, it's not prime

Flag Modification

• If a divisor is found, we set is_prime_flag to False
• We use break to exit the loop as soon as a divisor is found

Result Return

• The function returns the final state of the flag
• True means the number is prime
• False means the number is not prime

Key Advantages of Flag Variable

• Simple and easy to understand
• Efficient for small to medium-sized numbers
• Provides a clear boolean result
• Stops checking as soon as a divisor is found

“Start your coding journey with our complimentary Python courses designed just for you — dive into Python programming fundamentals, explore key Python libraries, and engage with practical case studies!”

3. Prime Number Program in Python Using Break and Continue Method

def is_prime(number):
    # Handle edge cases
    if number < 2:
        return False
    
    # Check for divisibility from 2 to square root of the number
    for i in range(2, int(number**0.5) + 1):
        # If number is divisible by any value, it's not prime
        if number % i == 0:
            # Break the loop as soon as a divisor is found
            break
        
        # If no divisor found, continue checking
        continue
    else:
        # If loop completes without finding divisors, number is prime
        return True
    
    # If loop breaks due to finding a divisor, number is not prime
    return False

# Test the function with various numbers
test_numbers = [2, 3, 4, 5, 7, 10, 11, 13, 17, 20]

print("Prime Number Checking Results:")
for num in test_numbers:
    result = is_prime(num)
    print(f"{num} is {'prime' if result else 'not prime'}")

Output

Prime Number Checking Results:
2 is prime
3 is prime
4 is not prime
5 is prime
7 is prime
10 is not prime
11 is prime
13 is prime
17 is prime
20 is not prime

Explanation of Code

1. Function Definition:
2. • is_prime(number) takes a number as input and returns True if it's prime, False otherwise.
2. Edge Case Handling:
3. • If the number is less than 2, it returns False because prime numbers start from 2.
3. Divisibility Check:
4. • Loops from 2 to the square root of the number (optimization technique).
   • Checks if the number is divisible by any value in this range.
4. Break Statement:
5. • If a divisor is found, break immediately exits the loop.
   • This happens when number % i == 0 (number is perfectly divisible).
5. Continue Statement:
6. • continue is used to skip to the next iteration if no divisor is found.
   • In this implementation, it doesn't significantly change the logic but demonstrates its usage.
6. Else Clause with For Loop:
7. • If the loop completes without finding divisors, the else block is executed.
   • This indicates the number is prime.

Related Read:

• Break, Pass, and Continue Statement in Python
• Break Statement in Python

4. Python Program for Prime Number Using While Loop

def is_prime(number):
    # Check if the number is less than 2 (not prime)
    if number < 2:
        return False
    
    # Initialize the divisor
    divisor = 2
    
    # Use while loop to check divisibility
    while divisor * divisor <= number:
        # Check if the number is divisible by the current divisor
        if number % divisor == 0:
            # If divisible, it's not a prime number
            return False
        
        # Increment the divisor
        divisor += 1
    
    # If no divisors found, the number is prime
    return True

# Test the function
test_numbers = [2, 3, 4, 5, 7, 10, 11, 13, 17, 20]

# Print prime status for each number
for num in test_numbers:
    if is_prime(num):
        print(f"{num} is a prime number")
    else:
        print(f"{num} is not a prime number")

Output

2 is a prime number
3 is a prime number
4 is not a prime number
5 is a prime number
7 is a prime number
10 is not a prime number
11 is a prime number
13 is a prime number
17 is a prime number
20 is not a prime number

Explanation of Code

Function Definition

• We define a function is_prime() that takes a number as input
• This function will return True if the number is prime, False otherwise

Initial Check

• First, we check if the number is less than 2
• Numbers less than 2 are not considered prime
• If the number is less than 2, we immediately return False

While Loop Mechanism

• We start with a divisor of 2 (the smallest prime number)
• The while loop continues as long as the square of the divisor is less than or equal to the number
• This optimization reduces unnecessary iterations

Divisibility Check

• Inside the loop, we check if the number is divisible by the current divisor
• If the remainder is 0, the number is not prime
• We return False as soon as a divisor is found

Divisor Increment

• If no divisibility is found, we increment the divisor
• This allows us to check the next potential divisor

Prime Confirmation

• If the loop completes without finding any divisors, the number is prime
• We return True

Related Read

• Python While Loop

5. Python Code for Prime Number Using Math Module

import math

def is_prime_using_math(number):
    """
    Check if a given number is prime using the math module.
    
    A prime number is a natural number greater than 1 that is only divisible by 1 and itself.
    This method uses mathematical properties to efficiently check primality.
    """
    # Handle special cases
    if number <= 1:
        return False
    
    # 2 is the only even prime number
    if number == 2:
        return True
    
    # Even numbers greater than 2 are not prime
    if number % 2 == 0:
        return False
    
    # Use math.isqrt to find the integer square root efficiently
    # We only need to check divisors up to the square root of the number
    sqrt_number = math.isqrt(number)
    
    # Check for divisibility by odd numbers up to the square root
    for divisor in range(3, sqrt_number + 1, 2):
        # If the number is divisible by any odd number, it's not prime
        if number % divisor == 0:
            return False
    
    # If no divisors are found, the number is prime
    return True

# Example usage and demonstration
def demonstrate_prime_checking():
    # List of numbers to test
    test_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17, 19, 20, 29]
    
    print("Prime Number Checking Results:")
    print("-" * 30)
    
    for num in test_numbers:
        result = is_prime_using_math(num)
        print(f"{num} is {'prime' if result else 'not prime'}")

# Run the demonstration
demonstrate_prime_checking()

Output

Prime Number Checking Results:
------------------------------
1 is not prime
2 is prime
3 is prime
4 is not prime
5 is prime
6 is not prime
7 is prime
8 is not prime
9 is not prime
10 is not prime
11 is prime
12 is not prime
13 is prime
17 is prime
19 is prime
20 is not prime
29 is prime

Explanation

• Import the math module
• Define a function is_prime_using_math()
• Handle special cases (numbers ≤ 1, 2, even numbers)
• Calculate the integer square root using math.isqrt()
• Check divisibility by odd numbers up to the square root
• Return True if no divisors are found, False otherwise

6. Prime Number Code in Python Using Recursion Method

def is_prime_recursive(n, divisor=None):
    """
    Check if a number is prime using recursive approach
    
    Args:
    n (int): The number to check for primality
    divisor (int, optional): The current divisor to check against. 
                             Defaults to None for initial call.
    
    Returns:
    bool: True if the number is prime, False otherwise
    """
    # Handle special cases
    if n <= 1:
        return False
    
    # If no divisor specified, start with square root of n
    if divisor is None:
        divisor = int(n ** 0.5)
    
    # Base cases
    # If we've checked all potential divisors successfully, the number is prime
    if divisor == 1:
        return True
    
    # If the number is divisible, it's not prime
    if n % divisor == 0:
        return False
    
    # Recursively check with the next lower divisor
    return is_prime_recursive(n, divisor - 1)

# Test the function with different numbers
test_numbers = [2, 3, 4, 7, 10, 17, 20, 29]

print("Prime Number Recursion Test Results:")
for num in test_numbers:
    result = is_prime_recursive(num)
    print(f"{num} is {'prime' if result else 'not prime'}")

Output

Prime Number Recursion Test Results:
2 is prime
3 is prime
4 is not prime
7 is prime
10 is not prime
17 is prime
20 is not prime
29 is prime

Explanation

The recursive approach to checking prime numbers involves systematically testing potential divisors from the square root of the number down to 1. Instead of using a loop, we use recursive function calls to check divisibility.

Key Recursive Strategy:

1. Start with the divisor as the square root of the number
2. Recursively check divisibility by reducing the divisor
3. Use base cases to determine primality

Code Breakdown:

• The function is_prime_recursive() takes two parameters:
• • n: The number to check for primality
  • divisor: Optional parameter to track current divisor (defaults to None)

Recursion Logic:

• Special case handling for numbers ≤ 1 (not prime)
• If no divisor is specified, start with square root of n
• Base cases:
• • If divisor reaches 1, number is prime
  • If number is divisible by current divisor, it's not prime
• Recursive call with reduced divisor

Step-by-Step Explanation:

1. When checking if a number is prime, we start from its square root
2. We recursively divide the number by decreasing divisors
3. If any divisor divides the number exactly, it's not prime
4. If we reach 1 without finding any divisors, the number is prime

Related Read:

• Recursion in Python
• Python Recursive Function

7. Prime Number Code in Python Using sympy.isprime()

pip install sympy
# Import the isprime function from sympy library
from sympy import isprime

# Function to demonstrate prime number checking
def check_prime_numbers():
    # Test various numbers to demonstrate isprime() functionality
    test_numbers = [2, 7, 10, 17, 20, 29, 100, 997]
    
    # Iterate through each number and check its primality
    for number in test_numbers:
        # Use isprime() to determine if the number is prime
        if isprime(number):
            print(f"{number} is a prime number.")
        else:
            print(f"{number} is not a prime number.")

# Call the function to run the demonstration
check_prime_numbers()

Output

2 is a prime number.
7 is a prime number.
10 is not a prime number.
17 is a prime number.
20 is not a prime number.
29 is a prime number.
100 is not a prime number.
997 is a prime number.

Explanation of Code

Import the Method:

• We import isprime() from the sympy library
• This gives us direct access to an optimized prime checking function

Function Creation:

• We create a function check_prime_numbers() to demonstrate the method
• This allows us to test multiple numbers easily

Number Selection:

• We create a list test_numbers with various integers
• The list includes prime and non-prime numbers to show the method's versatility

Primality Testing:

• We use a for loop to iterate through each number
• isprime() returns True for prime numbers, False otherwise
• We use an if-else statement to print whether each number is prime

Method Advantages:

• Works efficiently for small and large numbers
• No need to implement complex prime-checking algorithms manually
• Highly reliable and mathematically accurate

8. Bonus: Large Number Primarily Test

# Large number primality test
large_number = 104729
print(f"{large_number} is prime: {isprime(large_number)}")
# Interactive user input
def interactive_prime_check():
    try:
        number = int(input("Enter a number to check if it's prime: "))
        if isprime(number):
            print(f"{number} is a prime number!")
        else:
            print(f"{number} is not a prime number.")
    except ValueError:
        print("Please enter a valid integer.")

Output

104729 is prime: True

Performance Analysis of Different Methods Using Time Complexity and Space Complexity

Note: The complexity of sympy.isprime() varies based on its internal optimizations for small and large numbers.

Related Read:

• Time and Space Complexity

How upGrad can help you?

With upGrad, you can access global standard education facilities right here in India. upGrad also offers free Python courses that come with certificates, making them an excellent opportunity if you're interested in data science and machine learning.

By enrolling in upGrad's Python courses, you can benefit from the knowledge and expertise of some of the best educators from around the world. These instructors understand the diverse challenges that Python programmers face and can provide guidance to help you navigate them effectively.

So, reach out to an upGrad counselor today to learn more about how you can benefit from a Python course.

Here are some of the best data science and machine learning courses offered by upGrad, designed to meet your learning needs:

• Professional Certificate Program in Business Analytics & Consulting in association with PwC India
• Advanced Certificate Program in Generative AI
• Post Graduate Certificate in Machine Learning and Deep Learning
• Post Graduate Certificate in Data Science & AI (Executive)
• Executive Program in Generative AI for Business Leaders
• Post Graduate Programme in Data Science & AI (Executive)
• Master of Science in Machine Learning & AI
• Master’s Degree in Artificial Intelligence and Data Science
• Doctor of Business Administration in Emerging Technologies with Specialization in Generative AI

Similar Reads: Top Trending Blogs of Python

• Pattern Program in Python
• Leap Year Program in Python
• Difference Between List and Tuple in Python
• Difference between List, Tuple, Set, and Dictionary in Python
• Order Precedence in Python

FAQ’s

1. How can I find the prime number in Python?

To determine if a number is prime in Python, you must check whether it is divisible only by 1 and itself. A basic method involves iterating through potential divisors up to the square root of the number. If no divisors are found, the number is considered prime. More efficient methods reduce the number of iterations by skipping even numbers and known multiples of smaller primes.

2. What is the formula for finding prime numbers?

There is no single formula to find all prime numbers, but algorithms like the Sieve of Eratosthenes efficiently identify primes up to a certain range by systematically eliminating multiples of each prime starting from 2. For individual numbers, divisibility checks are performed, often combined with mathematical optimizations such as checking divisors only up to the square root of the number.

3. What are the prime numbers from 0 to 100 in Python?

Prime numbers from 0 to 100 include:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

4. How to Check Prime Numbers in Python?

To check wheteher the given number is prime or not, you can use methods like:

• If-Else Statement/for else statement
• Flag Variable
• Break and Continue Method
• Using While Loop
• Math Module
• Using Recursions
• sympy.isprime() method

5. How to Generate Prime Numbers in Python?

Generating prime numbers can be done in two ways:

• Finite Range: Use algorithms like the Sieve of Eratosthenes or iterate through a range while checking each number’s primality.
• Infinite Sequence: Use a prime number generator that yields primes one at a time, suitable for cases where the number of primes required isn’t predefined.

6. How to Find Prime Number in Python with Function?

Using a function to check for prime numbers promotes reusability and clarity. The function takes a number as input and returns whether it’s prime. Functions can also encapsulate optimizations, like reducing the number of checks by skipping even numbers or iterating only up to the square root of the input. Check the blog to get more details.

7. How to check the Prime Number in Python without Loop?

To check the prime number in python, you can use the math module or sympy.isprime() function.

8. What is the fastest way to check the prime number in Python?

The fastest way to check for primality depends on the number size:

• Small Numbers: Use trial division with optimizations like checking up to the square root and skipping even numbers.
• Large Numbers: Apply probabilistic tests like the Miller-Rabin Primality Test for speed with acceptable accuracy. For cryptographic purposes, deterministic tests may be used.

Ready to challenge yourself? Take our Free Python Quiz!

Take Quiz