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. Further reading: Find GCD.

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. See also: Check Perfect Number in Java.

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. A closely related topic: Find Factors of a Number in Java.

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.

  • Avoid calling Math.sqrt() on every iteration. i * i <= num is the common shortcut, but it overflows for numbers close to Integer.MAX_VALUE (see the test below); i <= num / i is just as fast and always safe.

  • 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

Test It With TestNG — and Catch an Overflow Bug

public final class Primes {
    private Primes() { }

    /** Correct for every int, including Integer.MAX_VALUE. */
    public static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        for (int i = 3; i <= n / i; i += 2) {      // i <= n / i avoids i * i overflowing
            if (n % i == 0) return false;
        }
        return true;
    }

    /** The popular i * i form: fine for small n, but i * i overflows near Integer.MAX_VALUE. */
    public static boolean isPrimeSquareCheck(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    /** Sieve of Eratosthenes: all primes up to limit. */
    public static boolean[] sieve(int limit) {
        boolean[] prime = new boolean[limit + 1];
        java.util.Arrays.fill(prime, 2, limit + 1, true);
        for (int i = 2; (long) i * i <= limit; i++) {
            if (prime[i]) for (int j = i * i; j <= limit; j += i) prime[j] = false;
        }
        return prime;
    }
}
import org.testng.Assert;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

public class PrimesTest {

    @DataProvider(name = "edgeCases")
    public Object[][] edgeCases() {
        return new Object[][] {
            { -7, false }, { 0, false }, { 1, false }, { 2, true }, { 3, true }, { 4, false },
            { 9, false },  { 25, false }, { 29, true }, { 97, true }, { 7919, true },
            { 2147483647, true },          // Integer.MAX_VALUE is prime (2^31 - 1)
            { 2147483646, false },
        };
    }

    @Test(dataProvider = "edgeCases")
    public void isPrimeHandlesEdgeCases(int n, boolean expected) {
        Assert.assertEquals(Primes.isPrime(n), expected);
    }

    @Test
    public void isPrimeAgreesWithTheSieveUpTo100000() {
        boolean[] sieve = Primes.sieve(100_000);
        for (int n = 0; n <= 100_000; n++) {
            Assert.assertEquals(Primes.isPrime(n), sieve[n]);
        }
    }

    @Test
    public void squareCheckIsWrongForIntegerMaxValue() {
        long start = System.currentTimeMillis();
        boolean result = Primes.isPrimeSquareCheck(Integer.MAX_VALUE);
        long ms = System.currentTimeMillis() - start;
        System.out.println("i * i version: isPrime(MAX_VALUE) = " + result + " in " + ms + " ms");
        Assert.assertEquals(result, true);
    }
}

Result:

PASS isPrimeAgreesWithTheSieveUpTo100000
PASS isPrimeHandlesEdgeCases × 13 (−7, 0, 1, 2, 3, 4, 9, 25, 29, 97, 7919, 2147483647, 2147483646)
i * i version: isPrime(MAX_VALUE) = false in 4022 ms
FAIL squareCheckIsWrongForIntegerMaxValue : expected [true] but found [false]
Total: 15, Passed: 14, Failed: 1

We compiled these tests with Java 21 and ran them with a minimal TestNG-compatible runner (the full TestNG library wasn't available in our environment); they use only standard TestNG annotations and Assert methods, so they run unchanged with mvn test in a TestNG project.

  • Cross-checking against a second algorithm is a powerful testing technique: the fast isPrime() agreed with the sieve for every number from 0 to 100,000.
  • The popular i * i <= num loop gave the wrong answer for Integer.MAX_VALUE — a prime — and took about 4 seconds. Once i passes 46,340, i * i overflows to a negative number, the condition stays true, and the loop keeps going until i reaches the number itself, which divides it. Writing i <= n / i avoids the multiplication entirely.
  • The edge cases every interviewer checks — negatives, 0, 1, 2 and small squares like 9 and 25 — are exactly where hand-written versions usually break.

Step through the loop for a small number like 29 and watch i stop at 5 in the Java Code Visualizer.

From Real Projects

My automation work has been in Java — Selenium WebDriver scripts with TestNG in Eclipse — and I use OOP concepts such as classes and objects, method overloading, overriding and constructors in page classes and utilities. Small programs like this one are the building blocks of real framework code: looping through data, comparing expected and actual values, and handling edge cases. On Canolog, the many forms and screens across sales, inventory, finance and service are where keeping page details in POM classes and reusable steps in a business library paid off. Test 0, 1, 2 and a large prime — the classic edge cases.

📖 Related tutorials

📚 Official documentation: dev.java: Learn Java (Oracle) · Java 21 API documentation

🧩 Java Number Programs — 11 of 41

← Previous: Check Leap Year in Java: Simple Logic + Full Code

Next: Check Palindrome Number in Java: Full Code + Logic →

See every program in the Java coding programs index.

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.