Check if a Number is Prime

• Prime number – an integer greater than one whose only positive divisors are 1 and itself.
• Square-root optimization – divisors come in pairs multiplying to N, so if no divisor exists up to sqrt(N), none exists at all.
• Loop bound – i * i <= n avoids a floating-point Math.sqrt and keeps the test in integers.
• Even shortcut – two is the only even prime; after checking two, loop only over odd candidates starting at three.
• Complexity – O(sqrt(n)) time, O(1) space for the trial-division approach.

What is a prime number?

A prime number is an integer greater than one that has no positive divisors other than one and itself. For example, 7 is prime because no number from 2 to 6 divides it evenly. 9 is not prime because 3 divides it.

Why check only up to the square root?

Divisors come in pairs that multiply to N. For 36, the pairs are (1,36), (2,18), (3,12), (4,9), (6,6). In every pair, one member is at most sqrt(N) and the other is at least sqrt(N). So if no divisor exists up to sqrt(N), none exists above it either. This reduces the work from O(n) to O(sqrt(n)).

How do you implement it in Java?

package com.bank.service;

public class PrimeChecker {

    public static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;         // only even prime
        if (n % 2 == 0) return false;    // eliminate all other evens
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        // Validate secure token candidates for National Bank of India
        int[] candidates = {2, 3, 4, 7, 9, 7919, 10000};
        for (int c : candidates) {
            System.out.println(c + " -> " + (isPrime(c) ? "PRIME" : "NOT PRIME"));
        }
    }
}

2 -> PRIME
3 -> PRIME
4 -> NOT PRIME
7 -> PRIME
9 -> NOT PRIME
7919 -> PRIME
10000 -> NOT PRIME

How is i * i <= n different from i <= Math.sqrt(n)?

| Feature | `i * i <= n` | `i <= Math.sqrt(n)` |
|---|---|---|
| Type | integer arithmetic | floating-point |
| Rounding risk | none | sqrt can round, missing edge |
| Overflow risk | yes, for large n | no |
| Performance | fast integer multiply | slower sqrt per iteration |

For most values i * i <= n is preferred. For N near Integer.MAX_VALUE, use i <= n / i to avoid overflow.

// Overflow-safe bound for large n
for (int i = 3; i <= n / i; i += 2) {
    if (n % i == 0) return false;
}

What are edge cases?

• 0 and 1 are not prime by definition.
• 2 is the smallest and only even prime.
• Negative numbers are not prime.

System.out.println(isPrime(0));  // false
System.out.println(isPrime(1));  // false
System.out.println(isPrime(2));  // true
System.out.println(isPrime(-7)); // false

What are common mistakes?

// Wrong: loop starts at 1 (1 divides everything)
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) return false; // always returns false!
}

// Wrong: loop goes to n instead of sqrt(n)
for (int i = 2; i < n; i++) { // works but O(n), way too slow
    if (n % i == 0) return false;
}

// Correct: starts at 2, stops at sqrt(n)
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
}

What about large primes and cryptography?

Trial division is fine for moderate numbers, but RSA keys use primes with hundreds of digits. For those, probabilistic tests like Miller-Rabin decide primality quickly with a negligible error chance. Java provides BigInteger.isProbablePrime(certainty) which runs Miller-Rabin internally.

import java.math.BigInteger;

BigInteger large = new BigInteger("104729");
System.out.println(large.isProbablePrime(20)); // true with high certainty

What should a senior engineer know?

A senior engineer knows that primality testing connects a simple loop to real financial security. The RSA keys that secure banking communications at National Bank of India depend on the difficulty of factoring the product of two large primes. Trial division checks small configuration parameters, but BigInteger.isProbablePrime handles cryptographic sizes.

For generating all primes up to N, the Sieve of Eratosthenes is far more efficient than testing each number individually.

What are common interview follow-up questions?

• How would you generate all primes up to N? (Sieve of Eratosthenes)
• What is the time complexity of trial division versus Miller-Rabin?
• Can you prove that divisors come in pairs below and above the square root?