Write a Java Program to find whether a number is prime or not in the most efficient way?

A prime number is a number greater than 1 that has exactly two factors: 1 and itself.

The most efficient approach for checking whether a number is prime is to test divisibility only up to the square root of the number. If a number has a factor greater than its square root, the corresponding factor must already exist below the square root.

Additionally, after checking divisibility by 2, only odd numbers need to be tested because an even number greater than 2 cannot be prime.

Java Solution:

public class PrimeNumber {

    public static boolean isPrime(int number) {

        if (number <= 1) {
            return false;
        }

        if (number == 2) {
            return true;
        }

        if (number % 2 == 0) {
            return false;
        }

        for (int divisor = 3; divisor * divisor <= number; divisor += 2) {
            if (number % divisor == 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {

        int number = 29;

        if (isPrime(number)) {
            System.out.println(number + " is a Prime Number.");
        } else {
            System.out.println(number + " is not a Prime Number.");
        }
    }
}

Output: 29 is a Prime Number.

Time Complexity: O(√n), because the algorithm checks divisibility only up to the square root of the number.

Space Complexity: O(1), as only a few additional variables are used regardless of the input size.

Key Interview Points: • A prime number has exactly two factors: 1 and itself. • Checking divisibility up to √n significantly reduces the number of iterations compared to checking up to n. • After handling 2 separately, only odd divisors need to be checked. • A common interview follow-up is to print all prime numbers within a given range using the Sieve of Eratosthenes algorithm.