How To Check Whether Number Is Prime Using Python

Prime numbers are integers greater than 1 that have only two positive divisors: 1 and themselves. They hold significant importance in mathematics and computer science, finding applications in various algorithms and cryptographic systems. In this tutorial, you will learn how to write a Python program to check whether a given number is prime or not.

What is a Prime Number?

Before diving into the Python code, let’s understand the concept of prime numbers. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, etc., are prime numbers.

Approach to Check Prime Numbers:

To determine whether a number is prime, we can follow a simple algorithm:

1. If the number is less than or equal to 1, it’s not prime.
2. If the number is 2, it’s prime.
3. If the number is even (except 2), it’s not prime.
4. Check for divisibility by odd numbers from 3 up to the square root of the number.

Python Code to Check Prime Numbers:

Now, let’s implement the above algorithm in Python:

import math

def is_prime(num):
    if num <= 1:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False
    else:
        # Iterate through odd numbers up to the square root of num
        for i in range(3, int(math.sqrt(num)) + 1, 2):
            if num % i == 0:
                return False
        return True

# Test the function
number = int(input("Enter a number: "))
if is_prime(number):
    print(number, "is a prime number")
else:
    print(number, "is not a prime number")

Enter a number: 61
61 is a prime number

Explanation of the Code:

• The is_prime function takes a number as input and returns True if it’s prime and False otherwise.
• It first handles edge cases where the number is less than or equal to 1, equal to 2, or even.
• Then, it iterates through odd numbers from 3 up to the square root of the number and checks for divisibility.
• If the number is divisible by any of these odd numbers, it returns False, indicating that the number is not prime. Otherwise, it returns True.

Dealing with Large Numbers:

When dealing with large numbers, a more efficient approach is required for checking prime numbers. One such method is the Miller-Rabin primality test, which is probabilistic but highly accurate. Python’s sympy library provides an implementation of this test. Here’s how you can use it:

First, make sure you have sympy installed. You can install it via pip if you haven’t already:

pip install sympy

Then, you can use the sympy.isprime() function to check if a large number is prime. Here’s an example:

from sympy import isprime

# Check if a large number is prime
number = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
if isprime(number):
    print(number, "is a prime number")
else:
    print(number, "is not a prime number")

This function is quite efficient even for large numbers. However, do note that sympy’s isprime() function uses probabilistic methods for large numbers, so there’s a tiny chance it might return a false positive (very, very unlikely for large numbers). For cryptographic applications or situations where absolute certainty is required, you might need to employ deterministic primality tests, which are computationally more intensive.