☕ DSA Java Articles

Topics › Basics › Know Basic Maths

Check for Prime Number

Easy TUF ID 365 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an integer n. Return true if n is prime, that is, n > 1 and the only positive divisors of n are 1 and n itself. Return false otherwise. Note that 0 and 1 are not prime, and 2 is the only even prime.

Constraints: 0 ≤ n ≤ 2^31 - 1.

Example 1

n = 29
answer = true       // divisors: 1 and 29 only

Example 2

n = 25
answer = false      // 25 = 5 * 5

Example 3

n = 1
answer = false      // 1 has a single divisor, not two

Approach 1: Brute force, count the divisors

Intuition. Go straight from the definition: a prime has exactly two positive divisors. Count how many d in 1..n divide n and compare the count with 2. This automatically rejects 1 (one divisor) and, with the explicit n < 2 guard, 0 and negatives.

Algorithm.

  1. If n < 2 return false.
  2. divisors = 0. For d from 1 to n: if n % d == 0, divisors++.
  3. Return divisors == 2.
static boolean bruteForce(int n) {
    if (n < 2) return false;
    int divisors = 0;
    for (int d = 1; d <= n; d++) {
        if (n % d == 0) divisors++;
    }
    return divisors == 2;
}

Complexity. Time O(n), one modulo per candidate. For n near 2 × 10^9 that is far too slow. Space O(1).

A slightly smarter brute force loops d from 2 to n - 1 and returns false at the first divisor. Early exit helps for composites with a small factor, but a prime still costs O(n).

Approach 2: Better, stop at the square root

Intuition. Divisors pair up: if d divides n then so does n / d, and the smaller member of each pair is at most sqrt(n). So if n has any divisor other than 1 and n, it has one in 2..sqrt(n). Test only that range; if nothing divides n there, n is prime.

The loop condition is (long) d * d <= n rather than d <= Math.sqrt(n): integer arithmetic has no rounding issues at perfect squares, and the long cast keeps d * d from overflowing for n near Integer.MAX_VALUE (where d reaches 46341 and 46341^2 exceeds 2^31).

Algorithm.

  1. If n < 2 return false.
  2. For d = 2 while d * d ≤ n: if n % d == 0 return false.
  3. Return true.
static boolean better(int n) {
    if (n < 2) return false;
    for (int d = 2; (long) d * d <= n; d++) {
        if (n % d == 0) return false;
    }
    return true;
}

Dry run on n = 29: d = 2 (4 ≤ 29, 29 % 2 = 1), d = 3 (9 ≤ 29, 29 % 3 = 2), d = 4 (16 ≤ 29, 29 % 4 = 1), d = 5 (25 ≤ 29, 29 % 5 = 4), d = 6 (36 > 29, stop). No divisor found, true.

Dry run on n = 25: d = 2, d = 3, d = 4 do not divide; d = 5 (25 ≤ 25) divides, false. The <= is essential: with < the loop would stop before 5 and call 25 prime.

Complexity. Time O(sqrt(n)), at most about 46341 iterations for any int. Space O(1).

This is the answer interviewers expect for a single query. It is also the building block for divisor listing and factorisation.

Approach 3: Optimal, skip multiples of 2 and 3

Intuition. Still O(sqrt(n)), but we can test three times fewer candidates. After ruling out divisibility by 2 and 3, every remaining prime divisor is of the form 6k - 1 or 6k + 1: among any six consecutive integers 6k, 6k+1, ..., 6k+5, the ones at offsets 0, 2, 4 are even and the one at offset 3 is divisible by 3, leaving only offsets 1 and 5 (which is 6(k+1) - 1). So test 5, 7, then 11, 13, then 17, 19, and so on, stepping by 6.

Algorithm.

  1. If n < 2 return false. If n < 4 return true (that is 2 and 3).
  2. If n % 2 == 0 or n % 3 == 0 return false.
  3. For d = 5 while d * d ≤ n, stepping d += 6: if n % d == 0 or n % (d + 2) == 0, return false.
  4. Return true.
static boolean optimal(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 (int d = 5; (long) d * d <= n; d += 6) {
        if (n % d == 0 || n % (d + 2) == 0) return false;
    }
    return true;
}

Dry run on n = 49: not below 4, 49 % 2 = 1, 49 % 3 = 1; d = 5: 25 ≤ 49, 49 % 5 = 4, 49 % 7 = 0, return false. On n = 97: d = 5 (97 % 5 = 2, 97 % 7 = 6), d = 11 (121 > 97, stop), true.

Complexity. Time O(sqrt(n)) with roughly sqrt(n) / 3 modulo operations, so about 15000 for the largest int. Space O(1).

Is it worth it? For one query, barely. But this trial-division routine is called in a loop in problems like “count primes in a range” or “factorise every number in an array”, and a constant factor of three is real there. For truly many queries over a bounded range, precompute a sieve instead (see the related problems).

The tests check all three approaches against each other for every n up to 10000 (there are exactly 1229 primes in that range), then run the two fast versions on 10^9 + 7 (prime), 10^9 + 8 (even) and 2^31 - 1 (prime, and the input that exposes any d * d overflow).

Edge cases and pitfalls