Prime Numbers

What Is a Prime Number?

Before writing any code, let's understand the problem.

The first few prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

One useful observation:

2 is the only even prime number.

Every other even number is divisible by 2, so it cannot be prime.

How Do We Check Whether a Number Is Prime?

Suppose the input is n = 29.

We need to determine whether any number other than 1 and 29 divides it exactly.

The simplest idea is:

1. Start from 2.
2. Try dividing n by every number.
3. If n % i == 0, we found a divisor.
4. If no divisor is found, n is prime.

For 29, we would check:

29 % 229 % 329 % 4...29 % 28

None divide 29 evenly, so 29 is prime.

This solution is correct.

But there is a problem.

The First Solution Does Too Much Work

Imagine checking whether n = 1,000,000,007 is prime.

The naive approach may check almost one billion possible divisors in a single loop.

But do we really need to check that many?

This is where problem solving begins.

Instead of immediately optimizing the code, let's look for a property of numbers that allows us to prove that many checks are unnecessary.

The Key Observation: Factors Come in Pairs

Suppose two numbers multiply to n: a × b = n

Then a and b are factors of n.

Take n = 36. Its factor pairs are:

1 × 362 × 183 × 124 × 96 × 6

Notice what happens.

As one factor gets larger, its partner gets smaller.

The middle point is √36 = 6.

After 6, the factor pairs simply repeat in reverse:

9 × 412 × 318 × 236 × 1

This gives us an important rule:

If a number is composite, at least one of its factors must be less than or equal to √n.

Why?

Suppose both factors were greater than √n:

a > √nb > √n

Multiplying them gives:

a × b > √n × √na × b > n

But we already know that a × b = n.

That is impossible.

Therefore, at least one factor must be ≤ √n.

And that changes our entire solution.

From the Observation to the Algorithm

We no longer need to check every number from 2 to n - 1.

We only need to check possible divisors up to √n.

For example, to check n = 91 we only need to go up to √91 ≈ 9.5.

So we check 2, 3, 4, 5, 6, 7, 8, 9.

At 7, we find that 91 % 7 == 0, so 91 = 7 × 13.

We can immediately conclude that 91 is not prime.

There is no reason to continue checking 10 through 90.

This is the important problem-solving lesson:

We are not making the loop faster by accident. We proved that the remaining work is unnecessary.

Building the Solution Step by Step

Let's turn the reasoning into code.

Step 1: Handle Numbers That Cannot Be Prime

A prime number must be greater than 1. So n ≤ 1 means not prime.

Step 2: Check Possible Divisors

Start from 2 and continue while i × i ≤ n.

This condition is equivalent to i ≤ √n, but keeps the comparison in integer arithmetic.

Step 3: Stop When a Divisor Is Found

If n % i == 0, then n has a divisor other than 1 and itself, so n is not prime.

Step 4: If Nothing Divides It

If we reach the end without finding a divisor, n is prime.

The Implementation

Here is the complete solution:

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

The code directly follows the reasoning:

n ≤ 1   ↓not prime otherwise   ↓check divisors up to √n   ↓divisor found?   ├── yes → not prime   └── no  → prime

Can We Make It Slightly Faster?

Yes.

We already know that 2 is the only even prime.

So after checking 2, we don't need to test any other even number.

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

Now the loop checks only 3, 5, 7, 9, 11, ... instead of 2, 3, 4, 5, 6, 7, ....

The asymptotic complexity remains O(√n), but we perform fewer checks.

For a Foundation course, the first implementation is usually the better starting point because it is simpler. The optimized version is worth understanding once the core idea is clear.

Why i * i <= n?

You may wonder why we write i * i <= n instead of i <= Math.sqrt(n).

Both express the same mathematical boundary, because i² ≤ n means i ≤ √n.

Using i * i <= n keeps the calculation in integer arithmetic and avoids repeatedly computing a square root.

There is one implementation detail to remember: with very large integer values, i * i can overflow. A safer alternative is i <= n / i, or using a wider integer type where appropriate.

For normal Foundation-level inputs, i * i <= n is easy to understand and widely used.

Complexity: How Much Work Did We Remove?

The naive approach checks up to n - 1 possible divisors, which is O(n).

The optimized approach checks only up to √n, which is O(√n).

For n = 1,000,000,007 we do not need to check roughly one billion numbers. We only need to consider divisors up to about √n ≈ 31,623.

That is a huge reduction in work, and Big O notation is how we describe it.

This is an important DSA habit:

Before optimizing code, look for a property that lets you avoid doing the work in the first place.

Common Mistakes

Let's Test Our Reasoning

Consider n = 97. We only need to check possible divisors up to √97 ≈ 9.8, so we check 2, 3, 4, 5, 6, 7, 8, 9.

None divides 97. Therefore 97 is prime.

Now consider n = 100. We only need to go up to √100 = 10.

When we check 2, we find that 100 % 2 == 0. A divisor is found immediately, so 100 is not prime.

Notice that we did not need to inspect the remaining numbers.

Quick Check

A Different Question: All Primes Below n

Everything above answers one question: is this one number prime?

A related question sounds the same and is not: list every prime below n.

The tempting move is to call isPrime in a loop, once per number. That works and it is the wrong tool. Each call redoes work its neighbours already did, and the total lands around O(n√n).

The right tool is the Sieve of Eratosthenes. Instead of testing each number, it starts with every number marked prime, then walks up from 2 crossing off every multiple of each prime it finds. What is left standing is the answer, in roughly O(n log log n).

You do not need the implementation yet. What matters is the habit: "is it prime?" and "which are prime?" are different problems, and reaching for the answer to the first one to solve the second is the mistake an interviewer is watching for.

The Problem-Solving Pattern

The prime-number problem teaches more than primality testing.

When you encounter a problem that appears to require checking a huge number of possibilities, pause before writing the loop.

Ask:

1. What exactly am I looking for?
2. What is the simplest solution?
3. Am I checking things that cannot possibly change the answer?
4. Is there a mathematical or structural property that lets me eliminate them?
5. Can I stop as soon as the answer becomes certain?

For prime numbers, the answer came from factor pairs. That observation reduced "check up to n" to "check up to √n".

It is the same habit Leap Year asks for, applied to a different kind of rule: understand the structure of the problem before you write the condition.

This way of thinking will become increasingly important as you move into Data Structures and Algorithms.

Quick Recap

• A prime number is greater than 1 and has exactly two positive divisors.
• 1 is neither prime nor composite.
• The simplest solution tries possible divisors.
• Factors always occur in pairs.
• Every composite number has at least one factor ≤ √n.
• Therefore, checking beyond √n is unnecessary.
• The basic optimized solution runs in O(√n) time.
• We can skip even divisors after handling 2.
• The bigger lesson is to prove which work can be eliminated before optimizing the code.

Where This Leads

Conditions     ↓Loops     ↓Control Flow     ↓Leap Year, Prime Numbers     ↓Functions

Leap Year turned a set of rules into a condition. This chapter turned a property of numbers into a loop you can stop early. Both are the same move: understand the problem before writing the code.

The next step is wrapping work like this so it can be reused and reasoned about on its own, which is Functions.