Java Program to Check Prime Number: 5 Methods from Brute Force to Sieve

Q: How do I check if a number is prime in Java?

Return false for numbers below 2, then test divisors from 2 while i * i <= n. If none divides n, it is prime.

Q: How do I print prime numbers from 1 to 100 in Java?

Run a sieve up to 100 and print the numbers that are not crossed out, or call a square-root primality test in a loop. Both are shown above.

Q: What is the fastest prime check in Java?

For a single number, the 6k±1 loop. For a whole range, the sieve.

Q: Can Java check very large primes?

Yes: BigInteger.isProbablePrime works on arbitrarily large values.

Five ways to check a prime number in Java: naive, square root, 6k+-1, Sieve of Eratosthenes and BigInteger.isProbablePrime, with measured timings and a program to print primes in a range.

Ankur Oct 21, 2026 7 min read

A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The Java question is not “can you check one?” but “how fast, and for how many numbers?” This page gives five answers, measured:

Method	Idea	Time to test one n	Memory	Best for
Naive	Try every divisor 2..n−1	O(n)	O(1)	Teaching only
Square root	Stop at √n	O(√n)	O(1)	One-off checks
6k±1	Skip multiples of 2 and 3	O(√n), about a third of the divisors	O(1)	Fast single checks
Sieve of Eratosthenes	Cross out multiples once	O(n log log n) for all primes up to n	O(n)	Many primes in a range
BigInteger.isProbablePrime	Probabilistic test	Polylogarithmic in n	O(1)	Numbers beyond long

The short version: to test one number, stop at its square root (and skip multiples of 2 and 3 if you care). To list many primes, use a sieve. For numbers too big for a long, use BigInteger.isProbablePrime.

Tested on OpenJDK 21.0.12. Every output block below is copied from one run of PrimeNumbers.java. Timings are from a shared cloud sandbox, so treat the ratios as meaningful and the absolute milliseconds as approximate. Run javac PrimeNumbers.java && java PrimeNumbers on your machine.

The five methods

Method 1: Naive trial division

Try every number from 2 to n − 1. If any divides n, it is not prime. It is correct and slow: a prime n needs n − 2 divisions.

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

Source: PrimeNumbers.java.

Method 2: Stop at the square root

If n = a × b then one of the factors is at most √n, so any composite number has a divisor no bigger than √n. The loop condition i * i <= n avoids calling Math.sqrt.

Use long i, not int i. For n close to 2³¹, i * i overflows int and goes negative, so the loop never stops at the right place.

static boolean isPrimeSqrt(int n) {
    if (n < 2) return false;
    for (long i = 2; i * i <= n; i++) {          // long: i * i would overflow int near 2^31
        if (n % i == 0) return false;
    }
    return true;
}

Source: PrimeNumbers.java.

Method 3: 6k±1

Every prime above 3 is one more or one less than a multiple of 6 (the other residues are divisible by 2 or 3). So after handling 2 and 3 explicitly, test only 5, 7, 11, 13, 17, 19, …: that is i and i + 2 with i stepping by 6. You test about a third of the divisors the square-root loop tests.

static boolean isPrime6k(int n) {
    if (n < 2) return false;
    if (n < 4) return true;                      // 2 and 3
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long i = 5; i * i <= n; i += 6) {       // every prime > 3 is 6k-1 or 6k+1
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

Source: PrimeNumbers.java.

Method 4: Sieve of Eratosthenes

Instead of testing each number, cross out multiples. Start at 2, cross out 4, 6, 8, …; move to the next number that is not crossed out (3) and cross out its multiples starting from 9; and so on up to √limit. What is left is the primes.

The picture is the sieve on 2–30. Blue numbers are crossed out by 2, green by 3, amber by 5. The red numbers are what remain: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Only primes up to √30 ≈ 5.5 needed to do any crossing out; 7 and above crossed out nothing. The inner loop starts at p * p because smaller multiples were already crossed out by smaller primes.

static boolean[] sieve(int limit) {
    boolean[] composite = new boolean[limit + 1];
    for (int p = 2; (long) p * p <= limit; p++) {
        if (!composite[p]) {
            for (int m = p * p; m <= limit; m += p) composite[m] = true;
        }
    }
    return composite;                            // composite[i] == false and i >= 2  =>  prime
}

Source: PrimeNumbers.java.

Method 5: BigInteger.isProbablePrime

BigInteger.valueOf(n).isProbablePrime(certainty) runs randomized primality tests. The chance of a composite slipping through is below 2^−certainty. It is slower than trial division for small numbers (the objects cost more than the arithmetic) but it works on numbers with hundreds of digits, where trial division would never finish.

static boolean isPrimeBig(long n) {
    return BigInteger.valueOf(n).isProbablePrime(20);   // error chance below 2^-20
}

Source: PrimeNumbers.java.

Do all five agree?

Here is each method run on the same inputs, copied from the program output. The naive and sieve columns show - where the input was too large for them to be worth running.

n            naive  sqrt   6k+-1  sieve  BigInt
0            false  false  false  false  false
1            false  false  false  false  false
2            true   true   true   true   true
3            true   true   true   true   true
4            false  false  false  false  false
17           true   true   true   true   true
25           false  false  false  false  false
97           true   true   true   true   true
100          false  false  false  false  false
7919         true   true   true   true   true
1000000007   -      true   true   -      true

Source: PrimeNumbers.java.

How much faster is it, really?

Task	Naive	√n	6k±1	Sieve	BigInteger
All primes below 100,000 (9,592 primes)	1,002 ms	10 ms	4 ms	1 ms	560 ms
All primes below 10,000,000 (664,579 primes)	not run	6,315 ms	2,159 ms	105 ms	11,088 ms
Test the single number 1,000,000,007	2,208 ms	0 ms	0 ms	n/a	0 ms

Two things stand out. First, the naive loop is about 100 times slower than the square-root loop on 100,000 numbers, and testing one 10-digit prime takes 2,208 ms with naive and under a millisecond with the other methods. Second, the sieve beats everything when you want all primes in a range: it needed 105 ms for 10 million, where even the 6k±1 test needed 2,159 ms. The raw output:

Count primes below 100,000 (answer: 9592)
  naive : 1002 ms
  sqrt  : 10 ms
  6k+-1 : 4 ms
  sieve : 1 ms
  BigInt: 560 ms

Count primes below 10,000,000 (answer: 664579)
  sqrt  : 6315 ms
  6k+-1 : 2159 ms
  sieve : 105 ms
  BigInt: 11088 ms

One test of 1,000,000,007 (prime):
  naive : 2208 ms
  sqrt  : 0 ms
  6k+-1 : 0 ms
  BigInt: 0 ms
2^61-1 (Mersenne prime) via BigInteger: true

Source: PrimeNumbers.java.

Print primes in a range

Use the sieve up to the upper bound, then collect the unmarked numbers from from to to. For 10 to 50 this prints:

static List<Integer> primesInRange(int from, int to) {
    boolean[] composite = sieve(to);
    List<Integer> out = new ArrayList<>();
    for (int i = Math.max(2, from); i <= to; i++) {
        if (!composite[i]) out.add(i);
    }
    return out;
}

Primes in [10, 50]: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Source: PrimeNumbers.java.

Common interview questions

What is the most efficient way to check if a number is prime?

For one number, trial division up to its square root, skipping multiples of 2 and 3. For many numbers, a sieve. For huge numbers, a probabilistic test such as BigInteger.isProbablePrime.

Why do we only check up to the square root?

If n = a × b with both factors above √n, their product would exceed n. So a composite number always has a factor at most √n.

Is 1 a prime number?

No. A prime must have exactly two distinct divisors. 1 has one. The programs above return false for 0, 1 and negatives.

What is the time complexity of the Sieve of Eratosthenes?

O(n log log n) time and O(n) memory.

Is isProbablePrime always right?

If it says composite, the number is definitely composite. If it says prime, the chance of being wrong is below 2^−certainty.

Common mistakes

Calling 1 prime, or forgetting that 2 is the only even prime.
Using int for the loop variable with i * i <= n. It overflows near the top of the int range.
Looping to n / 2 and calling that optimised. It halves the work of the naive version; the square root removes almost all of it.
Allocating a sieve for an enormous limit. A boolean[] of 10 million entries is fine; a billion needs about 1 GB.
Benchmarking without warm-up. The first method timed pays for JIT compilation. The program above warms up first.

FAQ

How do I check if a number is prime in Java?

Return false for numbers below 2, then test divisors from 2 while i * i <= n. If none divides n, it is prime.

How do I print prime numbers from 1 to 100 in Java?

Run a sieve up to 100 and print the numbers that are not crossed out, or call a square-root primality test in a loop. Both are shown above.

What is the fastest prime check in Java?

For a single number, the 6k±1 loop. For a whole range, the sieve.

Can Java check very large primes?

Yes: BigInteger.isProbablePrime works on arbitrarily large values.

Java Program to Check Prime Number: 5 Methods from Brute Force to Sieve

The five methods

Do all five agree?

How much faster is it, really?

Print primes in a range

Common interview questions

Common mistakes

FAQ

How do I check if a number is prime in Java?

How do I print prime numbers from 1 to 100 in Java?

What is the fastest prime check in Java?

Can Java check very large primes?

Further reading

Related

No Comments yet!

Leave a ReplyCancel reply