Check if a Number is Prime or Not | Maths Playlist

A comprehensive exploration of prime numbers, examining the limitations of naive definitions and algorithms, and developing an optimal solution using square root factor symmetry and time-complexity reduction.

1. Defining a Prime Number: Precision Matters

When asked for the definition of a prime number, people often reply: "A number that is divisible by one and itself."

However, this definition is imprecise and fails edge cases.

The Problem with the Naive Definition

If a prime number is defined only as "divisible by 1 and itself," let's test it against $N = 1$ :

Is $1$ divisible by $1$ ? Yes.
Is $1$ divisible by "itself" ( $1$ )? Yes.
Therefore, under the loose definition, $1$ would be classified as a prime number.
Reality: $1$ is not a prime number.

The Correct Mathematical Definition

Note: A prime number is a number strictly greater than $1$ that has exactly two distinct positive divisors: 1 and the number itself (N).

Let's test numbers against this rigorous standard:

$N = 1$ : Divisors = {1} (Total = 1 divisor). Not Prime.
$N = 2$ : Divisors = {1, 2} (Total = 2 divisors). Prime.
$N = 5$ : Divisors = {1, 5} (Total = 2 divisors). Prime.
$N = 10$ : Divisors = {1, 2, 5, 10} (Total = 4 divisors). Not Prime.
$N = 13$ : Divisors = {1, 13} (Total = 2 divisors). Prime.

2. The Naive Approach: Linear Scan ( $O(N)$ )

The most direct way to check if a number is prime is to inspect every integer from $1$ up to $N$ , counting how many numbers divide $N$ evenly.

Naive Algorithm Implementation

C++

bool isPrimeNaive(int n) {
    int counter = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            counter++;
        }
    }
    // A prime number must have exactly 2 divisors
    if (counter == 2) {
        return true;
    }
    return false;
}

Complexity Analysis

Time Complexity: $O(N)$ because the loop iterates $N$ times. If $N = 10^9$ , the algorithm performs one billion operations.
Space Complexity: $O(1)$ because only a primitive counter variable is maintained in memory.

In a technical interview or high-throughput production environment, an $O(N)$ solution for large inputs is unacceptable. We need an optimization.

3. Core Mental Model: Factor Symmetry and Square Roots

To optimize our prime-checking algorithm, we can leverage the mathematical property of divisor symmetry explored when finding all divisors of a number.

Real-Life Analogy: Finding Rectangular Plots

Imagine you are asked to find all possible distinct rectangular dimensions (width $\times$ height) that can form an area of $36$ square units.

If you list them out as pairs $(i, \text{other divisor})$ where $i \times \text{other divisor} = 36$ :

$1 \times 36 = 36$ (Pairs: 1 and 36)
$2 \times 18 = 36$ (Pairs: 2 and 18)
$3 \times 12 = 36$ (Pairs: 3 and 12)
$4 \times 9 = 36$ (Pairs: 4 and 9)
$6 \times 6 = 36$ (Pairs: 6 and 6) — The turning point
$9 \times 4 = 36$ (Pairs: 9 and 4) — The pairs start repeating in reverse order!

Structure & Concept Flow

Divisor Pairs for 36:

1 -----> 36

2 -----> 18

3 -----> 12

4 -----> 9

6 -----> 6 <--- [Square Root Boundary ($\sqrt{36} = 6$)]

9 -----> 4 (Repeats)

12 -----> 3 (Repeats)

Notice that all factors occur in pairs on either side of $\sqrt{N}$ . Once you cross $\sqrt{N}$ , the divisors simply mirror the ones you have already found. Therefore, you never need to search beyond $\sqrt{N}$ to find all factors.

4. Step-by-Step Evolution: Optimizing Divisor Counting

Let's apply the square root property to our divisor-counting logic. Instead of running our loop up to $N$ , we run it up to $\sqrt{N}$ .

Handling Dual Factors and Perfect Squares

When iterating up to $\sqrt{N}$ , whenever we find a divisor $i$ (such that $n \pmod i == 0$ ), we actually uncover two divisors simultaneously:

i
n / i (the counterpart divisor)

Crucial Edge Case (Perfect Squares): If $N = 36$ and $i = 6$ , then n / i is also $6$ . We must ensure we do not count $6$ twice!

If i is equal to n / i, we increment our counter by 1.
If i is not equal to n / i (e.g., $i = 2$ and $n / i = 18$ ), we increment our counter by 2.

5. Early Exit Optimization for Primality

Remember: our goal is not to list or count all divisors, but simply to answer: "Is this number prime?"

A prime number has at most two divisors ( $1$ and itself). If at any point during our iteration we discover a third divisor, we can immediately declare that the number is not prime and break out of the loop early, saving valuable CPU cycles.

Structure & Concept Flow

Start Loop (i = 1 to sqrt(N))

Is 'i' a divisor of N? --(No)--> Continue Loop

(Yes)

Increment counter (handle dual factor if n/i != i)

Does counter exceed 2? --(Yes)--> EXIT EARLY: Return FALSE (Not Prime)

(No)

Finish loop -> If counter == 2, Return TRUE (Prime)

6. Complete Optimized Code Implementation

Here is the clean, optimized C++ implementation incorporating the square root bound, duplicate checks, and early exit strategy:

C++

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false; // 1 and negative numbers are not prime

    int counter = 0;
    
    // Loop runs up to sqrt(n), expressed as (i * i <= n) to avoid floating-point inaccuracies
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            counter++; // Count 'i'
            
            // Count the counterpart divisor if it's different from 'i'
            if ((n / i) != i) {
                counter++;
            }
        }
        
        // Early exit optimization: if divisors exceed 2, it's not prime
        if (counter > 2) {
            return false;
        }
    }
    
    // A prime number will have exactly 2 divisors (1 and n)
    return (counter == 2);
}

int main() {
    int n = 37;
    if (isPrime(n)) {
        cout << n << " is a Prime Number." << endl;
    } else {
        cout << n << " is NOT a Prime Number." << endl;
    }
    return 0;
}

7. Comparative Strategy Analysis

Approach	Loop Condition	Time Complexity	Space Complexity	Early Exit / Efficiency
Naive Scan	`i <= n`	$O(N)$	$O(1)$	None. Iterates fully through all numbers.
Square Root Scan	`i * i <= n`	$O(\sqrt{N})$	$O(1)$	Stops at $\sqrt{N}$ , drastically reduces iterations for large numbers.
Optimized Early Exit	`i * i <= n` with break	$O(\sqrt{N})$ worst-case, $O(1)$ best-case	$O(1)$	Terminates instantly upon finding a composite factor.

Summary and Key Takeaways

Redefining Primes: A prime number is strictly greater than $1$ and has exactly two divisors: $1$ and itself. This correctly excludes $1$ from being classified as prime.
The Naive Flaw: Checking divisibility up to $N$ results in an inefficient $O(N)$ linear time complexity.
Divisor Symmetry: Factors always exist in pairs that mirror each other across the square root of the number ( $\sqrt{N}$ ).
Loop Boundary Optimization: By running the loop only while $i \times i \le N$ , we reduce the time complexity from $O(N)$ to $O(\sqrt{N})$ .
Handling Counterparts: When $N \pmod i == 0$ , account for both $i$ and $N / i$ , taking care not to double-count perfect square roots (e.g., $6 \times 6 = 36$ ).
Early Termination: Because primality only requires knowing if divisors exceed two, breaking out of the loop the moment counter > 2 optimizes execution for composite numbers.
Space Efficiency: All algorithms discussed operate in $O(1)$ auxiliary space since only scalar tracking variables are used.