Prime Numbers

What is a prime number?

Imagine you have 12 square stones. Can you arrange them into a neat solid rectangle more than one stone wide? Easily: 2 rows of 6, or 3 rows of 4. 12 breaks into smaller pieces.
Now try doing that with 7 stones. You cannot make 2 equal rows, or 3, or 4. The only rectangle you can build is a single line of 7 stones.
7 cannot be assembled from smaller whole-number blocks. Numbers like that are the primes: the indivisible atoms of arithmetic.

A prime number is a whole number strictly greater than 1 that cannot be formed by multiplying two smaller positive integers. Its only divisors are 1 and itself.

Numbers with more than two factors are called composite. The number 1 is neither: by definition, primes must have exactly two distinct positive divisors.

The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, and 19. Notice that 2 is the only even prime number; every subsequent even number is divisible by 2 and therefore composite.

The naive test and why it slows down

The most direct way to test whether a number n is prime is trial division: try dividing n by every candidate number from 2 up to n - 1.

If any candidate divides n evenly (n % i == 0), n is composite. If you test every integer up to n - 1 and find no divisors, n is prime.

This works for small numbers. But if n is one billion (1,000,000,007), testing a billion numbers in a loop takes measurable seconds. You are doing far more work than mathematics requires.

The square root breakthrough

You never need to search all the way to n - 1. You only need to search up to √n.

Here is why: factors always travel in pairs.

If a × b = n, then one factor must be less than or equal to √n, and the other must be greater than or equal to √n. If both factors were strictly larger than √n, their product would exceed n.

Take n = 36, where √36 = 6:

1 × 36 = 36
2 × 18 = 36
3 × 12 = 36
4 × 9 = 36
6 × 6 = 36 (the square root pivot)
9 × 4 = 36 (mirror of 4 × 9)
12 × 3 = 36 (mirror of 3 × 12)
18 × 2 = 36 (mirror of 2 × 18)

Once you check up to 6, every larger factor is just the mirror partner of a smaller factor you already checked. If 36 had no factors at or below 6, it could not possibly have any above 6.

For n = 1,000,000,007, √n is roughly 31,622. Checking 31,622 numbers instead of one billion drops the runtime from seconds to less than a millisecond. In Big O terms, this improves trial division from O(n) to O(√n).

Checking primes in Java

Here is the standard, optimized primality check in Java:

Code

public class PrimeCheck {  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;  }}

Two design decisions make this code fast and reliable:

i * i <= n instead of Math.sqrt(n): Computing Math.sqrt converts integers to floating-point numbers on every iteration, which introduces overhead and subtle precision issues. i * i <= n stays entirely within integer arithmetic.
i += 2: We handle 2 upfront. Once 2 is ruled out, no even divisor can ever divide n, so the loop skips all even numbers (3, 5, 7, 9, etc.).

Edge cases and common mistakes

Watch out

Assuming 1 is prime: 1 has only one positive divisor (itself). A prime must have exactly two distinct positive divisors.
Negative numbers and 0: None of these are prime. Always guard with if (n <= 1) return false;.
Integer overflow on large inputs: If $n$ is large, i * i can exceed the maximum value of a 32-bit integer and wrap into negative numbers, creating an infinite loop. When working near integer limits, write i <= n / i or declare i as a long.

Quick check

Every composite number has at least one factor at or below its square root. If no number up to √n divides n, nothing above it ever will.