Java Prime Number Checker Program: Efficiently Check if a Number is Prime

Checking if a number is prime might seem like a small task, but it’s a classic for a reason. It’s a perfect exercise for beginners, touching on everything from loops to conditional logic. Plus, once you get the hang of writing efficient code for this task, you’ll be on your way to tackling more complex problems. In this article, we’ll walk through building a Java Prime Number Checker—and we’ll even add some optimizations to make the program faster, especially for larger numbers.

Let’s jump in!

What’s a Prime Number, Anyway?

If you haven’t covered prime numbers in a while, here’s a quick refresher. A prime number is a whole number greater than 1 that has no divisors other than 1 and itself. So, for instance:

• Prime numbers include 2, 3, 5, 7, and 11—these only divide evenly by 1 and themselves.
• Non-prime numbers (also called composite numbers) have more than two divisors. Take 4, for example; it can be divided evenly by 1, 2, and 4, so it’s not prime.

Prime numbers are like the “atoms” of arithmetic—building blocks that other numbers are composed of, so they come up often in math and computing.

First Steps: A Basic Prime Checker Program

Let’s start with a basic approach. The goal is simple: write a Java program that checks if a user’s number is prime. For this first version, we’ll do it the straightforward way—by checking each number up to n − 1 and seeing if any of them divide evenly into our target number, nnn. If any do, we know nnn isn’t prime.

Here’s how that looks in code:

import java.util.Scanner;

public class PrimeCheckerBasic {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter a number to check if it’s prime: ");
        int number = scanner.nextInt();

        boolean isPrime = true;

        if (number <= 1) {
            isPrime = false;
        } else {
            for (int i = 2; i < number; i++) {
                if (number % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        if (isPrime) {
            System.out.println(number + " is a prime number.");
        } else {
            System.out.println(number + " is not a prime number.");
        }
        
        scanner.close();
    }
}

Breaking It Down

The code might seem complex at first, but it’s straightforward when you walk through it:

1. Getting User Input: We start by taking an integer input from the user, which they want to check for “primeness.”
2. Handling Simple Cases First: Numbers less than 2 aren’t prime, so if the input is 1 or below, we set isPrime to false right away.
3. Looping Through Possible Divisors: For numbers 2 and up, we start a loop from 2 and go up to n−1n-1n−1, checking if any number divides evenly (i.e., number % i == 0). If we find such a divisor, the number isn’t prime.
4. Displaying Results: Finally, we print out whether the number is prime or not.

Optimizing the Prime Checker Program

While the above approach works, it’s not very efficient. Imagine checking if 100,003 is prime—you’d go through every number from 2 to 100,002! Thankfully, there are two optimizations that can make our code faster.

Optimization 1: Only Check Up to the Square Root

Instead of checking all the way to n−1n-1n−1, we only need to go up to the square root of nnn. Here’s why: if a number nnn has a factor larger than its square root, it also has a factor smaller than its square root. By stopping at the square root, we catch any smaller factors first, reducing the number of checks significantly.

Optimization 2: Skip Even Numbers (Except 2)

Apart from 2, no even numbers can be prime. So, after checking for 2, we can safely skip all even numbers. This change cuts down our work by half.

Here’s the optimized code:

import java.util.Scanner;

public class PrimeCheckerOptimized {

    public static boolean isPrime(int number) {
        // Handle cases for numbers less than 2
        if (number <= 1) {
            return false;
        }

        // Handle case for number 2, which is prime
        if (number == 2) {
            return true;
        }

        // Skip even numbers greater than 2
        if (number % 2 == 0) {
            return false;
        }

        // Only check odd divisors up to the square root of the number
        int sqrt = (int) Math.sqrt(number);
        for (int i = 3; i <= sqrt; i += 2) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter a number to check if it’s prime: ");
        int number = scanner.nextInt();

        if (isPrime(number)) {
            System.out.println(number + " is a prime number.");
        } else {
            System.out.println(number + " is not a prime number.");
        }
        
        scanner.close();
    }
}

Walking Through the Optimized Code

With these changes, the code is both faster and easier to follow. Here’s a breakdown:

1. Skip Low Numbers Right Away: Any number less than 2 isn’t prime, and we handle this with an early check.
2. Handle 2 as a Special Case: 2 is the only even prime number, so we check for it separately.
3. Ignore Even Numbers Beyond 2: For any other even number, we return false immediately, saving unnecessary checks.
4. Limit Looping to the Square Root: Using Math.sqrt(number), we calculate the square root once and loop only up to that point. This allows us to check just the smaller possible divisors, making the code more efficient.

Why These Optimizations Matter

To see why this is useful, let’s say you want to check if 100,003 is prime. In the basic code, you’d have to check 100,001 possible divisors. With these optimizations, you only check about 158 numbers, making a huge difference in efficiency.

Running the Optimized Program

1. Save the code as PrimeCheckerOptimized.java.
2. Open a terminal, navigate to the file’s directory, and compile it:

javac PrimeCheckerOptimized.java

3. Run it with:

java PrimeCheckerOptimized

Going Further

If you’re feeling adventurous, here are a few ways to expand this Java Prime Number Checker:

1. Prime Range Checker: Instead of a single number, modify the program to check if each number in a range (say, 1 to 100) is prime.
2. Prime Factor Finder: Have the program list all divisors of a number, so if it’s not prime, the user can see what factors are responsible.
3. User-Friendly Output: Add comments to the output or use colors to make the results clearer, especially when running the program for larger ranges.

Final Words

In this guide, we covered how to write a Prime Number Program in Java using efficient techniques. By incorporating optimizations like checking only up to the square root and skipping even numbers, we sped up the process significantly. This project might be a stepping stone, but it’s a perfect example of how a few small tweaks can make your code cleaner, faster, and more effective.

With these fundamentals, you’re ready to tackle more advanced projects, so give it a shot!