Java Program to Check Whether a Number is Prime
A prime number is a whole number greater than 1 that can be divided evenly only by 1 and by itself. The first prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. A number greater than 1 that is not prime, such as 4, 9 or 15, is called a composite number. 0 and 1 are neither prime nor composite.
To check whether a number n is prime, try dividing it by the numbers from 2 upward. If any of them divides n with no remainder, n is not prime.
1. Check Prime Number Using a for Loop
The isPrime() method returns false for numbers below 2, then looks for a divisor between 2 and n - 1. As soon as one is found, there is no need to keep looking, so the method returns immediately.
public class PrimeCheck {
static boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false; // found a divisor
}
}
return true;
}
public static void main(String[] args) {
int[] numbers = {7, 16, 25, 29, 1};
for (int n : numbers) {
System.out.println(n + (isPrime(n) ? " is a prime number." : " is not a prime number."));
}
}
}7 is a prime number. 16 is not a prime number. 25 is not a prime number. 29 is a prime number. 1 is not a prime number.
2. Check Prime Number Using a while Loop and User Input
This version reads the number from the user and uses a while loop with a boolean flag.
import java.util.Scanner;
public class PrimeCheckWhile {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = scanner.nextInt();
scanner.close();
boolean isPrime = n >= 2;
int i = 2;
while (isPrime && i < n) {
if (n % i == 0) {
isPrime = false;
}
i++;
}
System.out.println(n + (isPrime ? " is a prime number." : " is not a prime number."));
}
}Enter a number: 11 11 is a prime number.
Enter a number: 15 15 is not a prime number.
3. Faster Prime Check Up to the Square Root
Divisors come in pairs: if 36 = 4 × 9, one of the two factors is at most √36 = 6. So if n has no divisor up to √n, it has none at all. Checking only up to the square root makes the program much faster for large numbers. The condition i * i <= n does this without calling Math.sqrt().
The program also skips even numbers after checking 2, which halves the work again.
public class PrimeCheckFast {
static boolean isPrime(long n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2; // 2 is the only even prime
for (long i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
long[] numbers = {2, 97, 221, 7919, 1_000_000_007L};
for (long n : numbers) {
System.out.println(n + " -> " + (isPrime(n) ? "prime" : "not prime"));
}
}
}2 -> prime 97 -> prime 221 -> not prime 7919 -> prime 1000000007 -> prime
221 is not prime because 221 = 13 × 17. 1,000,000,007 is prime, and the loop needs only about 16,000 steps to show it instead of a billion.
4. Summary
- A prime number is greater than 1 and divisible only by 1 and itself.
- Return
falsefor numbers below 2, then look for a divisor starting from 2. - Stop as soon as a divisor is found; the number is not prime.
- Checking divisors only up to √n (
i * i <= n) gives the same answer much faster.