beginnerNumber ProblemsJava

Check Whether a Number Is Prime

Determine whether an integer greater than 1 has no divisors other than 1 and itself.

Quick Answer

A number is prime if it is greater than 1 and has no divisor other than 1 and itself. Test candidate divisors from 2 up to the square root of n; if any divides n evenly, it is not prime. Checking only up to the square root is enough because factors come in pairs.

Problem Statement

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. 2, 3, 5, 7, 11 are prime, while 4, 6, 9, 15 are not.

Given an integer n, return true if it is prime and false otherwise. For efficiency, test possible divisors only up to the square root of n, since any factor larger than the square root pairs with one smaller than it.

Input: A single integer n.

Output: true if n is prime, otherwise false.

Examples

Example 1
Input:  29
Output: true

29 has no divisor between 2 and 5 (its square root is about 5.39), so it is prime.

Example 2
Input:  15
Output: false

15 is divisible by 3, so it has a divisor other than 1 and itself and is not prime.

Constraints

  • n can be any 32-bit int; numbers less than 2 are not prime
  • Only test divisors up to sqrt(n) for efficiency

Think Before You Code

Reveal the questions to ask yourself first
  • Why are 0, 1, and negative numbers not prime?
  • Why is it enough to test divisors only up to the square root of n?
  • What is the very first divisor you should test?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
Handle the small cases first: any number below 2 is not prime.
Hint 2
You only need to test divisors from 2 up to the square root of n, not all the way to n.
Hint 3
Use the condition `i * i <= n` (with a long cast to avoid overflow) so you stop right at the square root.

Approach

Reveal the step-by-step approach

Rule out small values, then trial-divide up to the square root.

  1. If n < 2, return false.
  2. Loop i from 2 while i * i <= n:
    • If n % i == 0, n has a divisor other than 1 and itself, so return false.
  3. If no divisor is found, return true.

Cast i * i to long inside the loop condition so the multiplication cannot overflow for large n.

Dry Run

Walk through the example step by step

Checking n = 29:

i | i*i | i*i <= 29 | 29 % i
--+-----+-----------+-------
2 | 4   | yes       | 1
3 | 9   | yes       | 2
4 | 16  | yes       | 1
5 | 25  | yes       | 4
6 | 36  | no -> stop | —

No divisor found, so 29 is prime -> true.

Solution

Reveal the full Java solution
public class PrimeCheck {
    public static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; (long) i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPrime(29)); // true
        System.out.println(isPrime(15)); // false
    }
}

Every composite number n has a factor no larger than sqrt(n), because if both factors were bigger than the square root their product would exceed n. That is why looping while i * i <= n is enough and turns an O(n) scan into O(sqrt n).

Time: O(sqrt(n))Space: O(1)

Common Mistakes

  • Treating 1 (or 0 and negatives) as prime; primes must be greater than 1.
  • Looping i all the way to n instead of stopping at the square root, which is far slower.

Edge Cases to Test

  • 2 is the smallest and only even prime; the loop body never runs, so it returns true.
  • Perfect squares like 25 are caught when i reaches 5 (5 * 5 == 25).

Interview Follow-Ups

  • How would you generate all primes up to n efficiently with the Sieve of Eratosthenes?
  • How would you skip even divisors after checking 2 to roughly halve the work?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us