Java Program - Check Prime Number

Java Program – Check Prime Number

A prime number is a positive integer greater than 1 that has exactly two positive factors: 1 and the number itself. For example, 2, 3, 5, 7, and 11 are prime numbers, while 1, 4, 6, 8, and 9 are not prime numbers.

In Java, we can check whether a number is prime by testing whether any integer from 2 through its square root divides the number without leaving a remainder. The remainder is checked using the modulo operator %.

How to Check a Prime Number in Java

For an integer N, first check whether it is less than 2. Numbers less than 2 are not prime. For values of 2 or greater, test possible divisors beginning with 2. If N % i == 0 for any tested divisor i, the number is not prime.

It is not necessary to test every number up to N - 1. If N has a factor larger than its square root, the corresponding factor is smaller than its square root. Therefore, testing divisors only up to the square root is sufficient.

Prime Number Checking Algorithm

Read an integer N.
If N < 2, the number is not prime.
Initialize i to 2.
Continue while i <= N / i.
If N % i == 0, N has a divisor other than 1 and itself, so it is not prime.
Otherwise, increment i and test the next possible divisor.
If no divisor is found, N is prime.

The condition i <= N / i is an integer-arithmetic way to test divisors up to the square root of N. It also avoids the possible integer overflow that can occur with i * i <= N for very large integer values.

Java Program to Check Prime Number Using a for Loop

In the following program, we shall write a function isPrime(), using the above algorithm. This function takes a number as argument, then check if the number is prime or not, and returns a boolean value. The function returns true if the number is prime, else it returns false.

The following original example demonstrates the divisor loop for positive integers starting from 2. A later example on this page adds an explicit check for 0, 1, and negative integers.

Example.java

</>

Copy

/**
 * Java Program - Check if Number is Prime Number
 */

public class Example {

	public static void main(String[] args) {
		System.out.println("Is 32 prime : "+isPrime(32));
		System.out.println("Is 41 prime : "+isPrime(41));
	}
	
	public static boolean isPrime(int num) {	
		for(int i = 2; i <= num/i; ++i) {
			if(num % i == 0) {
				return false;
			}
		}
		return true;
	}
}

Run the above program, and you shall get the following output in the console.

Output

Is 32 prime : false
Is 41 prime : true

For 32, the first tested divisor is 2. Because 32 % 2 is 0, the function immediately returns false. For 41, none of the integers that need to be tested divides 41 evenly, so the function returns true.

Java Prime Number Program for 0, 1, and Negative Numbers

A complete prime-number method should explicitly reject every integer less than 2. This is important because 0, 1, and negative integers are not prime numbers.

</>

Copy

public class Example {
    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.");
        }
    }

    static boolean isPrime(int number) {
        if (number < 2) {
            return false;
        }

        for (int i = 2; i <= number / i; i++) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }
}

Output

29 is a prime number.

Java Program to Check Prime Number Using Scanner

When the number has to be entered by the user, use Scanner to read an integer from standard input. The prime-number test itself remains the same.

</>

Copy

import java.util.Scanner;

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

        System.out.print("Enter an integer: ");
        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();
    }

    static boolean isPrime(int number) {
        if (number < 2) {
            return false;
        }

        for (int i = 2; i <= number / i; i++) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }
}

For example, if the user enters 37, the result is:

Enter an integer: 37
37 is a prime number.

Why the Modulo Operator Finds Non-Prime Numbers

The expression number % i gives the remainder after dividing number by i. A remainder of zero means that i is an exact factor of the number.

17 % 2 is 1, so 2 is not a factor of 17.
17 % 3 is 2, so 3 is not a factor of 17.
21 % 3 is 0, so 3 is a factor of 21 and 21 is not prime.

Why the Loop Must Include the Square Root

The loop condition must include the square-root boundary. Consider 49. Its square root is 7, and 49 % 7 == 0. If the program stopped before testing 7, it could incorrectly classify 49 as prime.

That is why the examples use i <= number / i rather than a condition that excludes the boundary.

Print Prime Numbers from 1 to 100 in Java

The same isPrime() method can be reused to print all prime numbers in a range. The following program checks every integer from 1 through 100.

</>

Copy

public class Example {
    public static void main(String[] args) {
        for (int number = 1; number <= 100; number++) {
            if (isPrime(number)) {
                System.out.print(number + " ");
            }
        }
    }

    static boolean isPrime(int number) {
        if (number < 2) {
            return false;
        }

        for (int i = 2; i <= number / i; i++) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }
}

Output

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Prime Number Check Using a while Loop in Java

A while loop can implement the same prime-number test. The choice between for and while does not change the logic.

</>

Copy

static boolean isPrime(int number) {
    if (number < 2) {
        return false;
    }

    int i = 2;

    while (i <= number / i) {
        if (number % i == 0) {
            return false;
        }
        i++;
    }

    return true;
}

Prime Number Program Using a Divisor Count

Another beginner-friendly approach is to count how many positive integers divide the number exactly. A prime number has exactly two positive divisors. This method is easy to understand, but checking every value from 1 through the number performs more iterations than the square-root method.

</>

Copy

public class Example {
    public static void main(String[] args) {
        int number = 13;
        int count = 0;

        if (number > 1) {
            for (int i = 1; i <= number; i++) {
                if (number % i == 0) {
                    count++;
                }
            }
        }

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

Prime Number Edge Cases to Test in Java

When reviewing a Java prime-number program, test values that exercise the boundary conditions as well as ordinary prime and composite numbers.

Negative integer: -7 must return false.
Zero: 0 must return false.
One: 1 must return false.
Smallest prime: 2 must return true.
Odd prime: 3 or 41 must return true.
Even composite: 4 or 32 must return false.
Perfect square: 49 must return false, confirming that the square-root boundary is included.
Larger prime: 97 must return true.

Time and Space Complexity of the Prime Number Check

The square-root approach tests at most a number of divisors proportional to the square root of N. Its time complexity is O(sqrt(N)), and it uses O(1) additional space.

Prime Number Program Review Checklist

Confirm that integers less than 2 are treated as non-prime.
Confirm that the divisor loop starts at 2.
Confirm that the square-root boundary is included so perfect squares such as 49 are detected correctly.
Confirm that divisibility is tested with number % i == 0.
Confirm that the method returns immediately when a divisor is found.
Test both prime and composite inputs, including 2, 3, 4, 41, and 49.
When user input is used, confirm that Scanner reads an integer before the prime-number method is called.

Java Prime Number Program Summary

In this Java Tutorial, we learned how to write a Java Program to check if a given number is prime of not.

A reliable Java prime-number check first rejects values below 2, then tests possible divisors from 2 through the square root of the number. If any divisor produces a remainder of zero, the number is composite; otherwise, it is prime. The same method can be used with direct values, Scanner input, a for loop, a while loop, or when printing prime numbers across a range.

TutorialKart.com

Java Program – Check Prime Number