Program to check if a number is Prime

Prime numbers are the building blocks of mathematics and the foundation of modern computer cryptography. In Python, checking whether a number is prime is a classic programming exercise that tests your understanding of loops, conditionals, and algorithm optimization. Let's explore how to write this program, moving from a basic approach to a highly optimized one.

1. Conceptual Understanding: What is a Prime Number?

A Prime Number is a whole number strictly greater than 1 that has exactly two distinct positive divisors: 1 and itself. If a number can be divided evenly by any other number, it is considered a composite number.

The Rules of Primes:

• 0 and 1 are NOT prime numbers.
• 2 is the smallest and the only even prime number.
• Negative numbers are not considered prime.
• Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17...

2. Method 1: The Basic Approach (Brute Force)

The simplest way to check if a number n is prime is to try dividing it by every integer from 2 up to n - 1. If any of these divisions result in a remainder of 0, the number is not prime.

# Method 1: Basic loop checking all numbers up to n-1
num = int(input("Enter a number to check: "))

# Primes must be greater than 1
if num > 1:
    # Iterate from 2 to n-1
    for i in range(2, num):
        if (num % i) == 0:
            print(f"{num} is NOT a prime number.")
            print(f"Because {i} times {num//i} is {num}")
            break
    else:
        # This else belongs to the FOR loop, not the IF!
        # It triggers only if the loop completes without breaking.
        print(f"{num} IS a prime number.")
else:
    print(f"{num} is NOT a prime number.")

3. Method 2: The Optimized Approach (Square Root)

We can drastically optimize our code with a simple mathematical rule: A number n can only have a unique factor up to its square root.

For example, to check if 36 is prime, you only need to check up to 6 (the square root of 36). Any factor pair larger than 6 will just be the reverse of a pair you already found (e.g., if you found 3 × 12, you don't need to check 12 × 3). This drastically reduces the number of loops needed!

# Method 2: Optimized loop up to the square root
import math

def is_prime_optimized(n):
    if n <= 1:
        return False
    if n == 2:
        return True # 2 is the only even prime
    if n % 2 == 0:
        return False # Eliminate all other even numbers instantly
        
    # Check odd numbers from 3 up to the square root of n
    max_divisor = math.isqrt(n) 
    
    for i in range(3, max_divisor + 1, 2): # Step by 2 to skip evens
        if n % i == 0:
            return False
            
    return True

number = 999983
if is_prime_optimized(number):
    print(f"{number} IS a prime number.")
else:
    print(f"{number} is NOT a prime number.")