Prime Number Check Java | Fresher Interview

Direct Answer

A prime has exactly two divisors: 1 and itself. To test n, check divisibility only up to sqrt(n) - if no number in 2..sqrt(n) divides n, it's prime. That's O(sqrt(n)), far better than checking up to n. Handle edge cases: numbers < 2 are not prime. To find all primes up to n, use the Sieve of Eratosthenes in O(n log log n).

Deep Dive & Architecture

A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself. Numbers below 2 are not prime, and 2 is the smallest prime.

To test n, try possible divisors only while d <= n / d, which is an overflow-safe form of d * d <= n. If n has a factor larger than its square root, the matching factor must be smaller than the square root and would already have been found.

Worked example: 29

The square root of 29 is a little above 5, so test 2, 3, 4, and 5. None divides 29 exactly, so 29 is prime. For 35, divisor 5 gives remainder zero, so return false immediately; there is no reason to test later values.

After handling 2, an optimized loop can test only odd divisors 3, 5, 7, .... This halves unnecessary checks but does not change the O(√n) complexity. The method uses O(1) extra space.

Do not loop all the way to n - 1, which is O(n). Also avoid i * i <= n with large int values unless multiplication is widened to long, because integer overflow can make the condition incorrect.

Code Example

boolean isPrime(int n) {
    if (n < 2) return false;             // 0, 1, negatives: not prime
    for (int i = 2; (long) i * i <= n; i++) {   // only up to sqrt(n)
        if (n % i == 0) return false;    // found a divisor
    }
    return true;
}

// n = 37: check i=2..6 (since 6*6=36<=37, 7*7=49>37)
// none divide 37 -> prime
// n = 91: i=7 divides (7*13) -> not prime

Using i * i <= n avoids computing Math.sqrt and the floating-point edge cases.

Common Mistakes & Pitfalls

• Looping to n or n/2: only need up to sqrt(n) - factors pair up.
• Mishandling < 2: 0, 1, and negatives are not prime; return false early.
• Overflow in i*i: cast to long for large n.
• Math.sqrt rounding: prefer i * i <= n to avoid floating-point off-by-one.