How To Check If A Number Is Prime In Java

How to Check if a Number is Prime in Java

In the world of computer science, few concepts are as fundamental yet as powerful as the prime number. From securing internet communications to optimizing data structures, knowing how to identify these special integers is a crucial skill for any developer. If you are learning Java, one of the most common interview questions and practice exercises you will encounter is how to check if a number is prime in Java Most people skip this — try not to..

from the basics to more optimized solutions, ensuring you understand both the theory and the practical implementation.

The Basic Approach: Trial Division

The most straightforward method to check for primality is trial division. The idea is simple: a prime number is only divisible by 1 and itself. Because of this, we can test if the number is divisible by any integer from 2 up to the number itself minus one Small thing, real impact..

Here is the basic implementation in Java:

public static boolean isPrimeBasic(int num) {
    if (num <= 1) {
        return false; // 0 and 1 are not prime numbers
    }
    for (int i = 2; i < num; i++) {
        if (num % i == 0) {
            return false; // Divisible by another number, so not prime
        }
    }
    return true; // No divisors found, it's prime
}

While this method works, it is inefficient for large numbers because it performs num - 2 iterations in the worst case. We can optimize this significantly with a simple mathematical insight.

Optimizing the Loop Range

We don't need to check all the way up to num - 1. We only need to check up to 5 (the square root) to find a factor (5 itself). That said, for example, consider 25: its square root is 5. If a number num has a factor greater than its square root, the corresponding factor that pairs with it to yield num must be less than the square root. The factors are 1, 5, and 25. Which means, we can reduce the loop range to 2 through sqrt(num).

This optimization drastically reduces the number of iterations. For a large number like 10,000, the basic method would check 9,998 possibilities, while the optimized method checks only up to 100 (since √10,000 = 100) Worth keeping that in mind..

Here’s the optimized version:

public static boolean isPrimeOptimized(int num) {
    if (num <= 1) {
        return false;
    }
    // We only need to check up to the square root of num
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

Note the condition i * i <= num is used instead of i <= Math.sqrt(num) to avoid the potential floating-point inaccuracies and the performance overhead of calculating the square root repeatedly.

Handling Even Numbers

We can further optimize by handling the case of even numbers separately. But except for 2, all even numbers are composite. This allows us to check only odd divisors after verifying the number is not even.

public static boolean isPrimeFurtherOptimized(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2) {
        return true; // 2 is the only even prime number
    }
    if (num % 2 == 0) {
        return false; // All other even numbers are not prime
    }
    // Now check only odd divisors starting from 3
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

This version first eliminates even numbers quickly, then only tests odd numbers as potential divisors, cutting the number of checks in half.

Putting It All Together: A Complete Example

Let’s create a complete Java program that demonstrates these methods and tests them with a few numbers.

public class PrimeChecker {
    
    public static boolean isPrimeBasic(int num) {
        if (num <= 1) return false;
        for (int i = 2; i < num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public static boolean isPrimeOptimized(int num) {
        if (num <= 1) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public static boolean isPrimeFurtherOptimized(int num) {
        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public static void main(String