Check Prime Number in Python

A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Checking whether a number is prime is a common programming problem.

Concept Overview

A number is prime if it is not divisible by any number between 2 and its square root.

This reduces unnecessary computations.

Example

Input:
Number: 7

Output:
7 is a Prime Number

Method 1: Basic Approach

num = 7
is_prime = True

if num <= 1:
    is_prime = False
else:
    for i in range(2, num):
        if num % i == 0:
            is_prime = False
            break

if is_prime:
    print(f"{num} is a Prime Number")
else:
    print(f"{num} is Not a Prime Number")

Method 2: Optimized Approach (Square Root)

import math

num = 7
is_prime = True

if num <= 1:
    is_prime = False
else:
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            is_prime = False
            break

if is_prime:
    print(f"{num} is a Prime Number")
else:
    print(f"{num} is Not a Prime Number")

Output

7 is a Prime Number

Detailed Explanation

The optimized method reduces the number of iterations using square root logic.

If a number has a factor greater than its square root, it must also have a smaller factor.

This makes the algorithm faster.

Time and Space Complexity

Basic Method: O(n)

Optimized Method: O(√n)

Space Complexity: O(1)

Applications

Used in cryptography and security systems.

Important in number theory and algorithms.

Advantages

Efficient for small and medium numbers.

Easy to understand and implement.

Limitations

Not efficient for very large numbers without advanced algorithms.

Improvements You Can Make

Generate all prime numbers in a range.

Use Sieve of Eratosthenes for better performance.

Handle large inputs efficiently.

Understanding prime numbers is fundamental for advanced algorithms and problem solving.