How to Check If a Number Is Prime in Java

Introduction

In this lab, you will learn how to check if a number is prime in Java. We will start by implementing a basic loop to determine primality.

Next, we will optimize the prime checking process by utilizing the square root of the number. Finally, we will enhance the code to handle negative and non-integer inputs gracefully.

Implement Basic Prime Check Loop

In this step, we will write a Java program to check if a given number is a prime number using a basic loop. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Open the HelloJava.java file in the WebIDE editor if it's not already open.
Replace the entire contents of the file with the following code:
```
import java.util.Scanner;

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

        System.out.print("Enter a positive integer: ");
        int number = scanner.nextInt();

        if (number <= 1) {
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            for (int i = 2; i < number; i++) {
                if (number % i == 0) {
                    isPrime = false;
                    break; // Exit the loop early if a divisor is found
                }
            }

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

        scanner.close();
    }
}
```
Let's understand the new parts of this code:
- We still use the Scanner to get input from the user.
- int number = scanner.nextInt();: This line reads an integer value entered by the user and stores it in the number variable.
- if (number <= 1): We check if the number is less than or equal to 1. Numbers less than or equal to 1 are not considered prime.
- boolean isPrime = true;: We introduce a boolean variable called isPrime and initialize it to true. We'll use this to keep track of whether the number is prime.
- for (int i = 2; i < number; i++): This is a for loop. It starts with i at 2 and continues as long as i is less than the number. In each iteration, i increases by 1. We start checking for divisors from 2 because 1 is always a divisor and we are looking for divisors other than 1 and the number itself.
- if (number % i == 0): Inside the loop, this line checks if the number is perfectly divisible by i (the remainder of the division is 0). If it is, it means we found a divisor other than 1 and the number itself.
- isPrime = false;: If a divisor is found, we set isPrime to false.
- break;: This statement immediately exits the for loop. Once we find one divisor, we know the number is not prime, so there's no need to check further.
- Finally, we check the value of isPrime to print whether the number is prime or not.
Save the file (Ctrl+S or Cmd+S).
Compile the modified program in the Terminal:
```
javac HelloJava.java
```
If there are no compilation errors, a HelloJava.class file will be created.
Run the compiled program:
```
java HelloJava
```
The program will prompt you to enter a positive integer. Enter a number (e.g., 7) and press Enter. The program will tell you if the number is prime or not. Try entering different numbers like 4, 11, 1, or 0 to see the output.
```
Enter a positive integer: 7
7 is a prime number.
```
```
Enter a positive integer: 4
4 is not a prime number.
```

You have successfully implemented a basic prime number checker using a loop in Java!

Optimize Prime Check with Square Root

In the previous step, our prime checking loop iterated from 2 up to the number itself. While this works, it can be inefficient for very large numbers. We can optimize this by only checking for divisors up to the square root of the number.

Here's why this optimization works: If a number n has a divisor d greater than its square root (d > sqrt(n)), then there must be another divisor d' such that d * d' = n. This other divisor d' must be less than the square root (d' < sqrt(n)). Therefore, if a number has any divisors other than 1 and itself, it must have at least one divisor less than or equal to its square root. So, we only need to check for divisors up to the square root.

Open the HelloJava.java file in the WebIDE editor.

Modify the for loop in the main method to iterate only up to the square root of the number. Replace the existing for loop block with the following code:

// ... (previous code) ...

if (number <= 1) {
    System.out.println(number + " is not a prime number.");
} else {
    boolean isPrime = true;
    // Optimize the loop to check up to the square root
    int limit = (int) Math.sqrt(number);
    for (int i = 2; i <= limit; i++) {
        if (number % i == 0) {
            isPrime = false;
            break; // Exit the loop early if a divisor is found
        }
    }

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

// ... (rest of the code) ...

Let's look at the changes:

int limit = (int) Math.sqrt(number);: We calculate the square root of the number using Math.sqrt(). This method returns a double, so we cast it to an int because our loop counter i is an integer. We store this value in a variable called limit.
for (int i = 2; i <= limit; i++): The loop now iterates from 2 up to and including the calculated limit (the integer part of the square root).

Save the file (Ctrl+S or Cmd+S).
Compile the optimized program in the Terminal:
```
javac HelloJava.java
```
Again, if there are no errors, a HelloJava.class file will be generated.
Run the compiled program:
```
java HelloJava
```
Enter different numbers to test the optimized prime checker. You should get the same results as before, but for very large numbers, this version will be faster.
```
Enter a positive integer: 29
29 is a prime number.
```
```
Enter a positive integer: 100
100 is not a prime number.
```

You have successfully optimized your prime number checking program by reducing the number of iterations in the loop.

Handle Negative and Non-Integer Inputs

In the previous steps, our program assumes the user will always enter a positive integer. However, in real-world applications, users might enter negative numbers, zero, or even non-integer text. Our current program doesn't handle these cases gracefully. In this step, we will add checks to handle negative and non-integer inputs.

Open the HelloJava.java file in the WebIDE editor.

Modify the main method to include checks for negative numbers and use a loop to ensure the user enters a valid positive integer. Replace the existing code within the main method with the following:

import java.util.Scanner;
import java.util.InputMismatchException; // Import this class

public class HelloJava {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number = 0;
        boolean validInput = false;

        // Loop until valid positive integer input is received
        while (!validInput) {
            System.out.print("Enter a positive integer: ");
            try {
                number = scanner.nextInt();
                if (number > 0) {
                    validInput = true; // Input is valid, exit loop
                } else {
                    System.out.println("Please enter a positive integer (greater than 0).");
                }
            } catch (InputMismatchException e) {
                System.out.println("Invalid input. Please enter an integer.");
                scanner.next(); // Consume the invalid input to prevent infinite loop
            }
        }

        // Now, perform the prime check on the valid positive number
        if (number <= 1) { // This check is technically redundant now due to the input loop, but good for clarity
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            int limit = (int) Math.sqrt(number);
            for (int i = 2; i <= limit; 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();
    }
}

Let's break down the new additions:

import java.util.InputMismatchException;: We import this class to handle cases where the user enters something that is not an integer.
int number = 0; boolean validInput = false;: We initialize number and a boolean flag validInput.
while (!validInput): This is a while loop that will continue to execute as long as validInput is false.
try { ... } catch (InputMismatchException e) { ... }: This is a try-catch block. The code inside the try block is executed. If an InputMismatchException occurs (meaning the input wasn't an integer), the code inside the catch block is executed.
number = scanner.nextInt();: We attempt to read an integer.
if (number > 0): Inside the try block, we check if the entered number is positive. If it is, we set validInput to true to exit the loop.
System.out.println("Please enter a positive integer (greater than 0).");: If the number is not positive, we print an error message.
System.out.println("Invalid input. Please enter an integer.");: Inside the catch block, if an InputMismatchException occurs, we print an error message.
scanner.next();: This is crucial inside the catch block. It consumes the invalid input from the scanner, preventing an infinite loop where the program keeps trying to read the same invalid input.

Save the file (Ctrl+S or Cmd+S).
Compile the updated program:
```
javac HelloJava.java
```
Run the program:
```
java HelloJava
```

Now, try entering different types of input:

Enter a positive integer (e.g., 13).
Enter a negative integer (e.g., -5).
Enter zero (0).
Enter text (e.g., "hello").

Observe how the program handles these different inputs, prompting you to enter a valid positive integer until you do.

Enter a positive integer: -5
Please enter a positive integer (greater than 0).
Enter a positive integer: 0
Please enter a positive integer (greater than 0).
Enter a positive integer: hello
Invalid input. Please enter an integer.
Enter a positive integer: 17
17 is a prime number.

You have successfully made your prime checking program more robust by handling negative numbers and non-integer inputs using a loop and exception handling.

Summary

In this lab, we learned how to check if a number is prime in Java. We started by implementing a basic prime check using a loop that iterates from 2 up to the number minus one, checking for divisibility. This initial approach provided a fundamental understanding of the prime number definition and its algorithmic implementation.

We then explored optimizations to improve the efficiency of the prime check. This involved understanding that we only need to check for divisors up to the square root of the number, significantly reducing the number of iterations required for larger inputs. Finally, we addressed edge cases by handling negative numbers and non-integer inputs to make our prime checking function more robust and complete.