Python Program to Check Prime Number (Complete Guide)

Prime numbers are one of the most fundamental concepts in mathematics and computer science. A prime number is a number greater than 1 that has no divisors other than 1 and itself. Understanding prime numbers is essential for algorithm design, cryptography, and competitive programming.

In this comprehensive tutorial, we will explore multiple ways to check whether a number is prime in Python. We will cover beginner-friendly approaches as well as optimized methods used in real-world applications.

By the end of this tutorial, you will not only be able to write efficient prime-checking programs but also understand the logic behind them deeply.

1. Understanding Prime Numbers

A prime number is defined as a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself.

Prime Numbers: 2, 3, 5, 7, 11, 13
Non-Prime Numbers: 4, 6, 8, 9, 10

For example, the number 7 is prime because it is only divisible by 1 and 7. However, 8 is not prime because it is divisible by 1, 2, 4, and 8.

Understanding this concept is crucial before implementing any algorithm.

2. Basic Approach Using Loop

The simplest way to check if a number is prime is to try dividing it by all numbers from 2 to n-1. If any number divides it evenly, it is not prime.

num = int(input("Enter a number: "))

if num <= 1:
    print("Not Prime")
else:
    for i in range(2, num):
        if num % i == 0:
            print("Not Prime")
            break
    else:
        print("Prime")

This approach is easy to understand but inefficient for large numbers because it checks many unnecessary divisors.

3. Optimized Approach Using Square Root

A better approach is to check divisibility only up to the square root of the number. This significantly reduces the number of iterations.

import math

num = int(input("Enter a number: "))

if num <= 1:
    print("Not Prime")
else:
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            print("Not Prime")
            break
    else:
        print("Prime")

This method improves performance drastically and is commonly used in interviews.

4. Using Recursion

Recursion can also be used to check for prime numbers, although it is less efficient compared to iterative approaches.

def is_prime(n, i=2):
    if n <= 2:
        return True if n == 2 else False
    if n % i == 0:
        return False
    if i * i > n:
        return True
    return is_prime(n, i + 1)

num = int(input("Enter a number: "))

if is_prime(num):
    print("Prime")
else:
    print("Not Prime")

5. Advanced Techniques

For very large numbers, advanced algorithms like the Sieve of Eratosthenes and probabilistic tests (e.g., Miller-Rabin) are used.

n = 50
primes = [True] * (n + 1)
primes[0] = primes[1] = False

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

for i in range(2, n + 1):
    if primes[i]:
        print(i, end=' ')

This method is extremely efficient for generating multiple prime numbers.

6. Time Complexity Analysis

Basic approach: O(n) Optimized approach: O(√n) Sieve method: O(n log log n)

Understanding time complexity is important for writing efficient code.

7. Common Mistakes

1. Treating 1 as a prime number.

2. Not handling edge cases like 0 and negative numbers.

3. Using inefficient loops for large numbers.

4. Forgetting to break the loop when a divisor is found.

8. Real-World Applications

1. Cryptography (RSA encryption).

2. Hashing algorithms.

3. Competitive programming problems.

4. Mathematical research.

9. Practice Problems

1. Print all prime numbers in a range.

2. Count number of primes up to N.

3. Find twin primes.

4. Check prime using different methods.

Conclusion

Prime numbers are a core concept in programming and mathematics. Understanding different approaches—from basic loops to advanced algorithms—helps you write efficient and scalable solutions.

Mastering this topic will not only help in interviews but also strengthen your problem-solving skills for advanced programming challenges.