Java Program to Check Prime Number

You can check if a number is prime in Java by testing if it is divisible by any number from 2 to its square root using a loop like for (int i = 2; i <= Math.sqrt(n); i++) and returning false if divisible, otherwise true.

Examples

Input2

Output2 is a prime number

Input15

Output15 is not a prime number

Input17

Output17 is a prime number

How to Think About It

To check if a number is prime, think about whether it can be divided evenly by any number other than 1 and itself. Start checking from 2 up to the square root of the number because if it has a factor larger than its square root, the matching factor will be smaller and already checked. If you find any divisor, the number is not prime.

Algorithm

1

Get the input number n

2

If n is less than 2, return not prime

3

Loop i from 2 to square root of n

4

If n is divisible by i, return not prime

5

If no divisors found, return prime

Code

java

public class PrimeCheck {
    public static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    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");
        }
    }
}

Output

17 is a prime number

Dry Run

Let's trace the number 17 through the code

1

Check if number is less than 2

17 is not less than 2, continue

2

Start loop from 2 to sqrt(17) ≈ 4

Check divisibility by 2, 3, 4

3

Check divisibility by 2

17 % 2 = 1 (not zero), continue

4

Check divisibility by 3

17 % 3 = 2 (not zero), continue

5

Check divisibility by 4

17 % 4 = 1 (not zero), loop ends

6

No divisors found

Return true, 17 is prime

i	n % i	Divisible?
2	1	No
3	2	No
4	1	No

Why This Works

Step 1: Check small numbers

Numbers less than 2 are not prime by definition, so return false immediately.

Step 2: Loop to square root

Checking divisors only up to the square root is enough because larger factors would have smaller matching factors already checked.

Step 3: Return result

If no divisor divides the number evenly, it is prime, so return true.

Alternative Approaches

Check divisibility up to n-1

java

public static boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Simple but slower for large numbers because it checks more divisors.

Use 6k ± 1 optimization

java

public static boolean isPrime(int n) {
    if (n <= 3) return n > 1;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

More efficient by skipping multiples of 2 and 3.

Complexity: O(√n) time, O(1) space

Time Complexity

The loop runs up to the square root of n, so the time grows roughly with √n.

Space Complexity

Only a few variables are used, so space is constant O(1).

Which Approach is Fastest?

The 6k ± 1 method is faster than checking all numbers up to √n because it skips multiples of 2 and 3.

Approach	Time	Space	Best For
Check up to n-1	O(n)	O(1)	Very small numbers or learning
Check up to √n	O(√n)	O(1)	General use, balanced speed
6k ± 1 optimization	O(√n/3)	O(1)	Faster checks for larger numbers