Check Prime Number in Java
Problem
A prime number is a number greater than 1 that has exactly two factors: 1 and itself.
Given an integer, determine whether it is a prime number.
Java Program
public class PrimeCheck {
public static void main(String[] args) {
int n = 29;
boolean isPrime = n > 1; // numbers 1 and below are never prime
// Only check divisors up to sqrt(n) — any factor beyond that has a matching smaller one
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
isPrime = false;
break; // found a divisor, no need to keep checking
}
}
System.out.println(n + " is prime: " + isPrime);
}
}Output
Core Logic
You only need to test divisors up to the square root of the number — anything larger would already have a smaller matching factor.
- 1
isPrimestarts asn > 1, since numbers ≤ 1 are never prime. - 2The loop runs
ifrom 2 upward, but only whilei * i <= n— an integer-only stand-in for checking up to√n. - 3At each
i,n % i == 0checks whetheridividesnevenly. - 4If a divisor is found,
isPrimeis set tofalseandbreakexits the loop immediately. - 5If the loop finishes with no divisor found,
nis confirmed prime.
n = 29, the loop checks i = 2 through 5 (since 6 * 6 = 36 > 29), finds no divisor, and reports 29 as prime.Key Point: Using i * i <= n instead of Math.sqrt(n) avoids floating-point comparison and keeps the bound check a cheap integer multiply.
Why: The loop only tests divisors up to √n before stopping, and tracks state in a single boolean variable.
Key Concepts
Approach 2: BigInteger.isProbablePrime()
import java.math.BigInteger;
public class PrimeCheckBigInteger {
public static void main(String[] args) {
int n = 29;
// isProbablePrime() runs a Miller-Rabin test with a certainty of 100
boolean isPrime = BigInteger.valueOf(n).isProbablePrime(100);
System.out.println(n + " is prime: " + isPrime);
}
}
Output
Core Logic
Java's BigInteger class already knows how to test primality — no need to write the divisor loop yourself.
- 1
BigInteger.valueOf(n)wraps theintinto aBigInteger. - 2
.isProbablePrime(100)runs a probabilistic primality test (Miller–Rabin) with a certainty parameter of100. - 3The certainty parameter controls the probability of a false positive — higher values make a wrong answer astronomically unlikely.
BigInteger.valueOf(29).isProbablePrime(100) returns true.Key Point: 'Probable' isn't a red flag here — with a certainty of 100, the chance of a composite number being misreported as prime is far smaller than the chance of a hardware error, and this scales to numbers far too large for a trial-division loop to check quickly.
Why: Miller–Rabin runs k rounds of modular exponentiation, each costing roughly O(log² n), and BigInteger stores the number's digits proportional to its bit length.
Key Concepts
Approach 3: Java 8
import java.util.stream.IntStream;
public class PrimeCheckStream {
public static void main(String[] args) {
int n = 29;
// noneMatch() short-circuits as soon as a divisor is found, same as the loop's break
boolean isPrime = n > 1 && IntStream.rangeClosed(2, (int) Math.sqrt(n))
.noneMatch(i -> n % i == 0);
System.out.println(n + " is prime: " + isPrime);
}
}
Output
Core Logic
The same square-root-bound divisor check can be expressed as a single stream query — none of the candidate divisors evenly divide n.
- 1
IntStream.rangeClosed(2, (int) Math.sqrt(n))generates the same candidate divisors the loop checked, from2up to√n. - 2
.noneMatch(i -> n % i == 0)tests every candidate and returnstrueonly if none of them dividenevenly. - 3The result is combined with
n > 1using&&, since numbers 1 and below are never prime.
n = 29, the range is 2 through 5; noneMatch() checks all four and finds no divisor, so the expression evaluates to true.Key Point: noneMatch() short-circuits the same way the loop's break did — it stops checking as soon as a divisor is found, so there's no extra cost for composite numbers.
Why: IntStream.rangeClosed().noneMatch() still checks the same divisors up to √n and short-circuits on the first match, without building any collection.
Key Concepts
Interview Questions
Why check divisors only up to the square root of n?
If n = a × b and both a and b were larger than √n, their product would be bigger than n. So any composite number has a divisor no larger than √n, and checking up to there is enough.
Can the check skip even numbers?
Yes. After handling 2 separately, test only odd divisors: start at 3 and step by 2. That halves the work, and a further refinement checks only numbers of the form 6k ± 1.
Are 0 and 1 prime?
No. A prime must be greater than 1 and have exactly two divisors. Every prime check should return false for n <= 1 before the loop starts.