Introduction

Checking whether a number is prime is one of the most frequently asked Java programming interview questions. While the basic concept is straightforward, the problem is designed to test your understanding of algorithm optimization and mathematical reasoning rather than just your ability to write a loop.

A simple solution checks every possible divisor, but an efficient solution recognizes an important mathematical property: you only need to test divisibility up to the square root of the number. This optimization reduces the number of checks dramatically and is considered the standard interview solution.

In this guide, you'll learn multiple approaches to checking prime numbers in Java, including the brute-force method, the square-root optimization, skipping even divisors, printing prime numbers in a range, and an introduction to the Sieve of Eratosthenes for generating many prime numbers efficiently.

Advertisement

What Is a Prime Number?

A prime number is a natural number greater than 1 that has exactly two positive divisors:

  • 1

  • The number itself

Examples of prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Numbers that have more than two divisors are called composite numbers.

Examples:

4 = 2 × 2
6 = 2 × 3
8 = 2 × 4
9 = 3 × 3

Important points:

  • 1 is not a prime number.

  • 0 is not prime.

  • Negative numbers are not prime.

Method 1: Brute Force Approach

This is the simplest solution.

The program checks every integer from 2 to num - 1.

Java Program

public class PrimeCheckBruteForce {

    public static void main(String[] args) {

        int num = 29;
        boolean isPrime = true;

        if (num <= 1) {
            isPrime = false;
        } else {

            for (int i = 2; i < num; i++) {

                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        System.out.println(
                num +
                (isPrime
                        ? " is a prime number."
                        : " is not a prime number.")
        );
    }
}

Output

29 is a prime number.

How It Works

The loop checks:

29 % 2
29 % 3
29 % 4
...
29 % 28

If any remainder equals 0, the number has another divisor and therefore is not prime.

Otherwise, it is prime.

Time Complexity

O(n)

This approach becomes inefficient for very large numbers.

Method 2: Optimized Using Square Root

This is the standard interview solution.

Mathematical Idea

Every factor larger than √n has a corresponding factor smaller than √n.

For example:

100

1 × 100
2 × 50
4 × 25
5 × 20
10 × 10

Notice that after 10, every remaining factor has already been paired with a smaller factor.

Therefore, checking beyond √100 is unnecessary.

Java Program

public class PrimeCheckOptimized {

    public static void main(String[] args) {

        int num = 29;
        boolean isPrime = true;

        if (num <= 1) {
            isPrime = false;
        } else {

            for (int i = 2; i <= Math.sqrt(num); i++) {

                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        System.out.println(
                num +
                (isPrime
                        ? " is a prime number."
                        : " is not a prime number.")
        );
    }
}

Output

29 is a prime number.

Time Complexity

O(√n)

This is dramatically faster than checking every possible divisor.

Method 3: Skip Even Numbers

After checking the special case for 2, every remaining even number can be ignored.

Java Program

public class PrimeCheckSkipEvens {

    public static void main(String[] args) {

        int num = 29;
        boolean isPrime = true;

        if (num <= 1) {

            isPrime = false;

        } else if (num == 2) {

            isPrime = true;

        } else if (num % 2 == 0) {

            isPrime = false;

        } else {

            for (int i = 3; i <= Math.sqrt(num); i += 2) {

                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        System.out.println(
                num +
                (isPrime
                        ? " is a prime number."
                        : " is not a prime number.")
        );
    }
}

Why This Is Faster

The loop checks only:

3
5
7
9
11
...

instead of

2
3
4
5
6
7
8
9
...

Nearly half of the divisor checks are eliminated.

Time complexity remains:

O(√n)

but with a smaller constant factor.

Method 4: Print Prime Numbers in a Range

A common interview variation is printing all prime numbers between two values.

Java Program

public class PrimesInRange {

    static boolean isPrime(int num) {

        if (num <= 1) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {

            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {

        int start = 1;
        int end = 50;

        System.out.println(
                "Prime numbers between "
                        + start
                        + " and "
                        + end
                        + ":"
        );

        for (int num = start; num <= end; num++) {

            if (isPrime(num)) {
                System.out.print(num + " ");
            }
        }
    }
}

Output

Prime numbers between 1 and 50:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Method 5: Sieve of Eratosthenes

If you need all prime numbers up to N, checking each number individually is inefficient.

Instead, use the Sieve of Eratosthenes.

Java Program

public class SieveOfEratosthenes {

    public static void main(String[] args) {

        int n = 50;

        boolean[] isComposite = new boolean[n + 1];

        for (int i = 2; i * i <= n; i++) {

            if (!isComposite[i]) {

                for (int j = i * i; j <= n; j += i) {
                    isComposite[j] = true;
                }
            }
        }

        System.out.println("Prime numbers up to " + n + ":");

        for (int i = 2; i <= n; i++) {

            if (!isComposite[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

Output

Prime numbers up to 50:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Time Complexity

O(n log log n)

This is the preferred algorithm when generating many prime numbers.

How Java Handles This Internally

Methods 1–3 use only primitive variables:

  • num

  • i

  • isPrime

These are stored on the stack.

Math.sqrt() performs a floating-point calculation internally without creating objects.

The range-checking method repeatedly calls isPrime(), creating one stack frame per method call.

The Sieve of Eratosthenes allocates a boolean array on the heap, trading memory for significantly improved performance.

Real-Life Analogy

Imagine arranging people into equal rows.

With 12 people, you can arrange:

2 × 6
3 × 4
4 × 3
6 × 2

There are several possible arrangements.

Now imagine 13 people.

You can only arrange them as:

1 × 13

or

13 × 1

There is no other way to divide them evenly.

That is exactly what makes 13 a prime number.

Comparison Table

Method Time Complexity Best Used When
Brute Force O(n) Learning the concept
Square Root Optimization O(√n) Standard interview solution
Skip Even Numbers O(√n) Faster single-number checks
Sieve of Eratosthenes O(n log log n) Finding all primes up to a limit

Best Practices

  • Always check num <= 1 first.

  • Prefer the square-root optimization for single-number checks.

  • Use i * i <= num instead of repeatedly calling Math.sqrt() in performance-sensitive code.

  • Create a reusable isPrime(int num) method instead of duplicating logic.

  • Use the Sieve of Eratosthenes when generating many prime numbers.

Common Mistakes

Forgetting That 1 Is Not Prime

Many beginners accidentally classify:

0
1

as prime numbers.

Always reject numbers less than or equal to 1.

Checking Every Divisor

Avoid:

for (int i = 2; i < num; i++)

Prefer:

for (int i = 2; i * i <= num; i++)

Using < Instead of <=

Incorrect:

i < Math.sqrt(num)

Correct:

i <= Math.sqrt(num)

Otherwise, perfect squares like 25 may be incorrectly classified as prime.

Calling Math.sqrt() Every Iteration

Repeated floating-point calculations are unnecessary.

A common optimization is:

for (int i = 2; i * i <= num; i++)

Confusing the Sieve with Single-Number Checking

The Sieve of Eratosthenes is designed for generating many prime numbers.

It is unnecessary if you're checking only one number.

Expert Tips

  • Mention the square-root optimization during interviews.

  • Explain why checking only up to √n works mathematically.

  • Use i * i <= num for optimal performance.

  • Know when to use the Sieve of Eratosthenes.

  • Handle edge cases (num <= 1) before starting divisor checks.

Pros and Cons

Method Advantages Disadvantages
Brute Force Easy to understand Slow for large numbers
Square Root Optimization Fast and interview standard Still slower than sieve for many numbers
Skip Even Numbers Fewer iterations Slightly more complex logic
Sieve of Eratosthenes Extremely efficient for ranges Uses additional memory

Frequently Asked Questions

What is the fastest way to check if a number is prime?

For checking a single number, use the square-root optimization.

Why do we check only up to the square root?

Because every factor larger than √n has a matching factor smaller than √n.

Is 1 a prime number?

No.

A prime number must have exactly two positive divisors.

Can negative numbers be prime?

No.

Prime numbers are defined only for natural numbers greater than 1.

What is the Sieve of Eratosthenes?

It is an efficient algorithm for generating all prime numbers up to a specified limit.

Why skip even numbers?

Every even number greater than 2 is divisible by 2 and therefore cannot be prime.

How do I print prime numbers in a range?

Loop through each number and apply an optimized isPrime() function.

What is the time complexity of brute force?

O(n)

What is the time complexity of the optimized method?

O(√n)

What is the time complexity of the Sieve of Eratosthenes?

O(n log log n)

Is this a common interview question?

Yes.

It is one of the most frequently asked Java programming interview questions because it tests both logic and algorithm optimization.

Which method should I use in production?

  • Use the square-root optimization for checking individual numbers.

  • Use the Sieve of Eratosthenes when generating many prime numbers.