Check if a Number is Prime - Java

Category: Easy | Concepts used: Divisibility, loop optimization (square root trick)

---

Problem Statement

Given a number n, check whether it’s a prime number — a number greater than 1 that has no divisors other than 1 and itself.

Input : n = 7      Output: true   (prime)
Input : n = 8       Output: false  (divisible by 2, 4)

Examples (with edge scenarios)

#	n	Output	Why
1	7	true	Only divisible by 1 and 7
2	8	false	Divisible by 2 and 4
3	1	false	By definition, 1 is not prime (a very common trap!)
4	0 or negative numbers	false	Primality is only defined for positive integers greater than 1
5	2	true	The only even prime number — a classic edge case interviewers test for

Common Fresher Mistake

Mistake	What happens	Fix
Forgetting that 1 is NOT prime	Wrongly returns true for n=1	Explicitly handle n <= 1 as false up front
Looping all the way up to n-1 to check divisors	Works, but wastes time checking unnecessary divisors	Only need to check up to √n — see Solution 2
Forgetting 2 is prime (since it’s even)	May wrongly special-case “even = not prime”	2 is prime; only even numbers greater than 2 are non-prime

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether zero and negative values are allowed, how large the input can be, and what should happen when an arithmetic result exceeds the chosen Java type. The examples use the contract stated in this article, but an interview answer should say these assumptions aloud.

Analogy: Sifting for Factor Pairs

Imagine you are looking for pairs of keys (divisors) that can unlock a lock (the number $n$):

• Keys always come in pairs. For example, if the lock is 36, the pairs are (1, 36), (2, 18), (3, 12), (4, 9), and (6, 6).
• Notice that in every pair, the smaller key is always less than or equal to the square root of the lock ($\sqrt{36} = 6$).
• Therefore, if you check all keys up to 6 and none of them fit the lock, you don’t need to waste time checking any keys greater than 6 (like 9, 12, or 18), because if a larger key could fit, its smaller partner would have already unlocked it!

---

Solution 1 — Check All Divisors from 2 to n-1 (Brute Force)

Intuition

The literal definition of “prime” is “no divisors other than 1 and itself.” So the most direct way to check is: try dividing n by every number from 2 up to n-1. If any of them divides evenly, n is not prime.

public class PrimeCheckBruteForce {
    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false; // 0, 1, and negatives are never prime
        }

for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false; // found a divisor -> not prime
            }
        }
        return true; // no divisors found -> prime
    }

public static void main(String[] args) {
        System.out.println(isPrime(7));  // true
        System.out.println(isPrime(8));   // false
        System.out.println(isPrime(1));    // false
        System.out.println(isPrime(2));    // true
    }
}

Output:

true
false
false
true

Dry Run (n = 8)

i=2: 8%2=0 -> divisor found -> return false  (immediately, no need to check 3,4,5,6,7)

Dry Run (n = 7)

i=2: 7%2=1 -> not divisible
i=3: 7%3=1 -> not divisible
i=4: 7%4=3 -> not divisible
i=5: 7%5=2 -> not divisible
i=6: 7%6=1 -> not divisible
Loop ends (i reached n=7) -> return true

Interviewer’s take

This is correct, but inefficient for large numbers — checking every single value up to n-1 does a lot of unnecessary work. Interviewers will almost always ask if you can reduce the number of checks.

Follow-up questions you might get:

• “Do you really need to check all the way up to n-1?” → leads to Solution 2 (the square root optimization).

---

Solution 2 — Check Divisors Only up to √n (Optimized, Recommended)

Intuition

If n has a divisor larger than √n, it must be paired with a smaller divisor that’s less than √n (since divisors come in pairs that multiply to n). For example, for n=36, the pair (4,9) both surround √36=6. So if no divisor exists up to √n, none can exist beyond it either — checking further is pointless.

public class PrimeCheckOptimized {
    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true; // the only even prime
        }
        if (n % 2 == 0) {
            return false; // other even numbers are never prime
        }

// only check odd divisors up to sqrt(n)
        for (int i = 3; (long) i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

public static void main(String[] args) {
        System.out.println(isPrime(7));   // true
        System.out.println(isPrime(97));   // true
        System.out.println(isPrime(100));  // false
    }
}

Output:

true
true
false

Dry Run (n = 97, √97 ≈ 9.8)

n=97 is odd, n != 2
Check odd i from 3 up while i*i <= 97:
i=3: 3*3=9<=97 -> 97%3 = 1 -> not divisible
i=5: 5*5=25<=97 -> 97%5 = 2 -> not divisible
i=7: 7*7=49<=97 -> 97%7 = 6 -> not divisible
i=9: 9*9=81<=97 -> 97%9 = 7 -> not divisible
i=11: 11*11=121 > 97 -> loop stops
No divisor found -> true  (97 is prime)

Interviewer’s take

This is the answer interviewers actually want. Reducing the check to just √n (and skipping even numbers after handling 2 separately) is a well-known, important optimization that dramatically speeds things up for large n (e.g., for n = 1,000,000, this checks ~500 numbers instead of ~1,000,000).

Follow-up questions you might get:

• “Why is it enough to check only up to √n?” → Because divisors always come in pairs (a, b) where a * b = n; if both a and b were greater than √n, their product would exceed n. So at least one of the pair must be ≤ √n.
• “Why skip even numbers after 2?” → Any even number greater than 2 is automatically divisible by 2, so it can never be prime — no need to test it as a divisor either.

---

📊 Visual Flowchart

graph TD
    Start["Input Number n"] --> Guard{"n <= 1?"}
    Guard -->|Yes| RetFalse["Return False"]
    Guard -->|No| CheckTwo{"n == 2?"}
    CheckTwo -->|Yes| RetTrue["Return True"]
    CheckTwo -->|No| CheckEven{"n % 2 == 0?"}
    CheckEven -->|Yes| RetFalse
    CheckEven -->|No| InitLoop["i = 3"]
    InitLoop --> LoopCond{"i * i <= n?"}
    LoopCond -->|Yes| DivCheck{"n % i == 0?"}
    DivCheck -->|Yes| RetFalse
    DivCheck -->|No| IncLoop["i += 2"]
    IncLoop --> LoopCond
    LoopCond -->|No| RetTrue

---

Final Verdict — Which Solution Should You Give?

Solution 1 (check up to n-1)  ──O(n), slow for large n──►  Okay to start with, but flag inefficiency
Solution 2 (check up to √n)   ──O(√n), efficient────────►   PREFERRED FINAL ANSWER

• Solution 2 is the expected final answer — the √n optimization is a classic, well-known technique, and interviewers specifically look for it here.
• Solution 1 is fine as a starting point to show correctness first, but should be optimized when discussed further.

---

Quick Recap

Approach	Time	Space	Interview Signal
Check up to n-1	O(n)	O(1)	Correct, but not optimal
Check up to √n (skip evens)	O(√n)	O(1)	Preferred