How to Check Prime Number in Java

What is a Prime Number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples: 2, 3, 5, 7, 11, 13...

Solutions

Method 1: Basic Approach

java

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

// Usage
System.out.println(isPrime(7));   // true
System.out.println(isPrime(10));  // false

Method 2: Optimized (Check up to √n)

java

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    // Check odd divisors up to √n
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    
    return true;
}

// Much faster for large numbers!
System.out.println(isPrime(97));  // true

Print Prime Numbers in Range

java

public static void printPrimes(int start, int end) {
    for (int i = start; i <= end; i++) {
        if (isPrime(i)) {
            System.out.print(i + " ");
        }
    }
}

// Usage
printPrimes(1, 50);
// Output: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Did You Know?

2 is the only even prime number! All other even numbers are divisible by 2. Also, there are infinitely many prime numbers, proven by Euclid around 300 BC!

Pro Tip

For finding many primes, use the Sieve of Eratosthenes algorithm:

java

// Find all primes up to n
public static List<Integer> sieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.add(i);
    }
    return primes;
}

Real-World Use Cases

Cryptography: RSA encryption uses large prime numbers
Hash tables: Prime-sized tables reduce collisions
Random number generation: Prime-based algorithms
Computer science: Algorithm optimization

›Short versionOpen if you only have a minute.

A prime has exactly two positive divisors: 1 and itself. 1 is not prime. 2 is prime.
A loop from 2 to n - 1 is correct and O(n). Stop at the square root.
i * i overflows int once i passes 46340, and a negative product makes the loop condition useless.
i <= Math.sqrt(n) recomputes a double on every test and can admit an extra iteration.

Prime check

Decide whether a number has exactly two positive divisors: 1 and itself.

Working approach

Reject anything less than 2.
Handle 2, skip the other evens, then test odd divisors.
Continue while i <= n / i so the bound stays inside int.

Walk the sample

Input 29
Divisors to test run from 2 through 5
None divides 29
29 is prime

The trap

The optimized loop i * i <= n looks safe on 97 and loops forever, or stops early, once i * i wraps for a large prime.

java

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

Why is for (int i = 2; i * i <= n; i++) unsafe near the top of the int range?

46341 * 46341 does not fit in an int. The product wraps negative, so i * i <= n stays true and the loop does not end.

Write i <= n / i. The division stays inside the type. 1 is still not prime, and 2 still is.

Time O(sqrt(n)), space O(1).

Easy to get wrong

Looping all the way to n - 1 when a square-root bound is enough.
Treating 1 as prime.