Check if a Number is Prime or Not | GFG

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Formally, n is prime ⇔ it cannot be written as a × b where a > 1 and b > 1.

Why this matters:

• Prime testing is foundational in number theory, cryptography (RSA keys!), hashing, random-number generators, and countless coding interview puzzles.
• Writing progressively faster primality checks trains your ability to reason about loops, divisors, and mathematical bounds.

Here’s the [Problem Link] to begin with.

Quick Examples

In the following sections we’ll build three increasingly efficient solutions.

Brute Force Solution

Intuition & Approach

The most straightforward idea is:

1. Edge Case: 1 is not prime.
2. Try every integer i from 2 up to n-1.
3. If any i divides n evenly (n % i == 0), n is composite; otherwise it’s prime.

Code Implementation

class Solution:
    def isPrime(self, n):
        if n == 1:                      # 1 is not prime
            return False
        # test every possible divisor from 2 up to n-1
        for i in range(2, n):
            if n % i == 0:              # found a divisor → not prime
                return False
        return True                     # no divisors found → prime

Code Explanation

• The for loop exhaustively checks all potential divisors.
• Early exit on the first successful division saves some time, but worst-case still touches every number below n.

Dry Run (n = 10)

1. i=2 → 10 % 2 == 0 → returns False.
2. Loop stops immediately.

Time & Space Complexity

• Time: O(n) (linear in n).
• Space: O(1) – constant auxiliary memory.

Conclusion

Elegant in its simplicity, but painfully slow for large numbers (think millions or cryptographic bit-lengths).

Better Solution (Half-Range Check)

Intuition & Approach

A composite number must have at least one factor ≤ n/2.
Therefore we only need to test divisors up to ⌊n/2⌋.

Code Implementation

class Solution:
    def isPrime(self, n):
        if n == 1:                      # still not prime
            return False
        # any factor bigger than n//2 leaves a co-factor < 2
        for i in range(2, n // 2 + 1):
            if n % i == 0:              # divisor found
                return False
        return True

Code Explanation

• Reduces the divisor range roughly by half, yet retains the same early-exit behavior.

Dry Run (n = 15)

Divisor loop iterates i = 2 … 7; finds i = 3 quickly, returns False.

Time & Space Complexity

• Time: O(n/2) → still expressed as O(n) (constants dropped).
• Space: O(1).

Conclusion

A modest improvement; still far from efficient when n is large.

Optimal Solution (Square-Root Bound)

Intuition & Approach

If n is composite, it can be factored into a × b = n.
At least one factor a ≤ √n.
So it suffices to test divisors only up to ⌊√n⌋.

Code Implementation

class Solution:
    def isPrime(self, n):
        if n == 1:                          # handle 1
            return False
        # only test up to √n
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:                  # divisor within √n found
                return False
        return True                         # prime if loop finishes

Code Explanation

• The loop bound int(n ** 0.5) + 1 computes the floor of √n and includes it.
• Once past that limit, any remaining divisor would pair with one below the limit, which we’d have already checked.

Dry Run (n = 29)

• √29 ≈ 5.38 → test i = 2,3,4,5.
• None divide evenly → returns True.
  (Brute force would have checked up to 28.)

Time & Space Complexity

• Time: O(√n) – a dramatic speedup, especially for big inputs.
• Space: O(1).

Conclusion

Using the square-root insight slashes runtime from linear to sub-linear, transforming primality testing into a practically instantaneous task for medium-sized integers. For industrial-strength cryptography you’d employ even faster algorithms (e.g., Miller–Rabin), but for typical interview constraints this √n approach is optimal and elegant.

Key Takeaways

1. Start simple, verify correctness, then refine the bounds.
2. Cutting the search space from n → n/2 → √n shows the power of mathematical reasoning.
3. These same bounding ideas generalize to many divisor-based and search problems.

Now you’re equipped with three tiers of prime-checking solutions, ready for anything from classroom exercises to tech-interview whiteboards!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.