Java Program to Find Prime Numbers

A prime number is a number that is divisible only by 1 and itself. So, numbers like 2, 3, 5, 7, and 11 are prime numbers, while 4, 6, and 9 are not.

In this article, we'll write a Java program using a straightforward approach to determine if a number is prime. This approach is perfect for beginners to grasp the underlying logic. We also suggest the how to optimize this simple program.

The Strategy 

To check if a number is prime:

• Start by assuming every number is prime. 
• For each number, we'll check if any numbers less than it (except 1) divide it without a remainder. 
• If we find any such number, our given number is not prime. 

The Java Program 

Let's get coding:

public class SimplePrimeFinder {

    public static void main(String[] args) {
        int number = 17;
        if (isPrime(number)) {
            System.out.println(number + " is a prime number!");
        } else {
            System.out.println(number + " is not a prime number.");
        }
    }

    public static boolean isPrime(int num) {
        // Step 1: Basic check for numbers less than 2
        if (num < 2) {
            return false;
        }

        // Step 2: Check divisibility
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;  // num is divisible by i, so it's not prime
            }
        }

        return true;  // if we made it here, num is prime
    }
}

Output:

17 is a prime number!

Explaining the Program 

Basic Check for Numbers Less Than 2:

        // Step 1: Basic check for numbers less than 2
        if (num < 2) {
            return false;
        }

Numbers less than 2 are not considered prime. So, we immediately return false. 

Check Divisibility:

        // Step 2: Check divisibility
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;  // num is divisible by i, so it's not prime
            }
        }

Here, we're using a loop that runs from 2 up to (but not including) the number we're checking. If our number (num) is divisible by any number in this range, it's not prime, so we return false. If we get through the entire loop without returning, then the number is prime.

While this approach is simple and easy to understand, it's not the most efficient. In our approach, if we're checking if 100 is prime, we're still checking numbers like 98 and 99, even though it's evident they won't be factors. As you advance in your coding journey, you'll come across optimized algorithms to handle such tasks more efficiently.

The Optimized Strategy

• If the number is less than 2, it's not prime. 
• If the number is 2, it's prime. 
• If the number is even (but not 2), it's not prime. 
• Check odd divisors up to the square root of the number. If none of them divides the number, it's prime. 

Optimized Java Program:

public class OptimizedPrimeFinder {

    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.");
        }
    }

    public static boolean isPrime(int num) {
        if (num < 2) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        
        int sqrt = (int) Math.sqrt(num);
        for (int i = 3; i <= sqrt; i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Output:

29 is a prime number!

Explanation: 

Numbers Less Than 2: Numbers less than 2 aren't prime. This is our first check. 

Number is 2: 2 is the only even prime number, so we return true immediately. 

Even Numbers (except 2): All even numbers, except 2, are divisible by 2 and hence are not prime.

Check Odd Divisors: We only check odd numbers because, beyond 2, no even number can be a factor of a prime. We check up to the square root (sqrt) of the number because of the paired factor property described earlier. 

With this optimized strategy, our program becomes much more efficient, especially for larger numbers. The time complexity gets reduced considerably.