Check Prime: check whether N is prime and print Yes or No

• Prime – an integer > 1 with no positive divisors other than 1 and itself.
• Square-root bound – divisors come in pairs; if none up to sqrt(N), none exist at all.
• Loop bound – i * i <= N avoids floating-point sqrt.
• Early break – one divisor is enough to decide composite.
• Even shortcut – check 2 separately, then test only odd candidates.

What is the flowchart algorithm?

Set a flag isPrime to true. Loop candidate divisors i from 2 while i*i <= N. If N % i == 0, set isPrime to false and break. After the loop, if isPrime is true, print Yes; otherwise print No.

package com.bank.service;

public class PrimeChecker {

    public static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("7 -> " + (isPrime(7) ? "Yes" : "No"));
        System.out.println("9 -> " + (isPrime(9) ? "Yes" : "No"));
    }
}

7 -> Yes
9 -> No

Why stop at the square root?

Divisors come in pairs: if d divides N, then N/d also divides N. One of each pair is at most sqrt(N). So if no divisor is found up to sqrt(N), none exists above it either. This reduces the time complexity from O(n) to O(sqrt(n)).

Why check 2 separately and then skip even candidates?

Two is the only even prime. After confirming N is not divisible by 2, every remaining candidate must be odd. Starting the loop at 3 and incrementing by 2 cuts the number of iterations roughly in half, from sqrt(N) down to sqrt(N)/2.

Why break on the first divisor?

One factor is enough to prove the number is composite. Continuing to check would waste time and not change the answer.

What are edge cases?

• N = 0 or 1: not prime.
• N = 2: the smallest and only even prime.
• N = 3: prime (loop does not run since 2*2=4 > 3, so no iterations).
• Large N near Integer.MAX_VALUE: use i * i <= n carefully or i <= n / i to avoid overflow when i * i exceeds int range.

What are common mistakes?

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

// Wrong: loop goes all the way to n
for (int i = 2; i < n; i++) { // O(n) instead of O(sqrt(n))

// Correct
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
}

How does the flag-based flowchart version look?

boolean isPrimeFlag = true;
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        isPrimeFlag = false;
        break; // early exit
    }
}
System.out.println(isPrimeFlag ? "Yes" : "No");

What about large primes?

For cryptographic-size primes (hundreds of digits), trial division is too slow. Java provides BigInteger.isProbablePrime(certainty) which runs Miller-Rabin internally and is fast for any size.

import java.math.BigInteger;

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

How is prime checking used in banking systems?

At National Bank of India, hash table sizes for in-memory caches are chosen as prime numbers. A prime modulus distributes keys more evenly across buckets, reducing collision chains. Rajesh validates candidate table sizes with the PrimeChecker before configuring the cache.

int candidateSize = 97;
if (PrimeChecker.isPrime(candidateSize)) {
    System.out.println(candidateSize + " is a valid hash table size");
}

What should a senior engineer know?

A senior engineer uses trial division only for small configuration parameters and switches to probabilistic tests for large values. The square-root optimization is the interview essential, and writing it as i * i <= n is cleaner than calling Math.sqrt. For finding all primes up to N, the Sieve of Eratosthenes is more efficient at O(n log log n) than running trial division on each number individually.

What are common interview follow-up questions?

• How would you find all primes up to N? (Sieve of Eratosthenes)
• What is the time complexity of trial division?
• Can you prove the square-root bound mathematically?