Primes and Composites

Factors, the starting point

A quick reminder from the last lesson. A factor (or divisor) of a whole number $n$ is a whole number greater than $0$ that divides $n$ leaving remainder $0$. To list the factors of $n$, you ask of each candidate “does it divide $n$ evenly?” The factors of $12$ are

because each of these divides $12$ with nothing left over, and no other whole number does. Two of those factors come free for every whole number greater than $1$. Every such number is always divisible by $1$ (one group containing everything) and by itself (one group the size of the whole number). So the real question, the one that sorts numbers into two camps, comes down to this. Does a number have only those two forced factors, or does it have more?

Defining prime and composite

This is the whole idea, stated carefully. We count only the distinct factors, and we work with whole numbers greater than $1$.

A whole number greater than $1$ is prime when it has exactly two distinct factors: $1$ and itself, and nothing in between. The number $7$ is prime because the only whole numbers that divide it are $1$ and $7$. Try anything else, say $2$, $3$, $4$, $5$, or $6$, and a remainder appears.

A whole number greater than $1$ is composite when it has more than two distinct factors. The number $12$ is composite because, beyond $1$ and $12$, the numbers $2, 3, 4,$ and $6$ also divide it. Having even one extra factor is enough to make a number composite.

Both of those claims are things you can check rather than take on trust. Below you choose how many dots there are and how many go in each row. When every row comes out full, the row width is a factor. When the last row is short, it is not, and the leftover dots are drawn hollow so you can count them.

Set the count to $12$ and walk the row width from $2$ up to $6$. Widths $2$, $3$, $4$ and $6$ all come out full, and only $5$ leaves anything over, so $12$ has factors to spare and is composite. Now set the count to $7$ and walk the same widths again. Every single one leaves a short row. Nothing between $1$ and $7$ divides it, which is exactly what makes $7$ prime, and you have now checked it rather than been told it.

Every whole number greater than $1$ falls into exactly one of these two groups, never both and never neither. Either its only factors are $1$ and itself (prime), or it has at least one more (composite). Here is the start of the list, sorted:

Why 1 is neither prime nor composite

The number $1$ looks like it might be prime, since nothing divides it except $1$. But run it through the definition exactly. A prime needs two distinct factors. The number $1$ has only one factor, namely $1$ itself: the "$1$" and the “itself” are the same number, so they do not count twice.

The exclusion of $1$ is not just a bookkeeping rule. It keeps every whole number’s breakdown into primes unique: if $1$ counted as prime, you could glue extra copies of it onto any breakdown ($6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3$) and never land on one settled answer. The next lesson, on prime factorization, depends on that uniqueness, which is why $1$ is kept out.

Why 2 is the only even prime

Look at the prime list again: $2, 3, 5, 7, 11, 13, \ldots$. After $2$, every entry is odd. That is no accident.

Try to find an even number past $2$ that survives the definition. Take $14$. Being even hands it $2$ as a factor for free, on top of the $1$ and the $14$ that every number is forced to have. Its factor list is $1, 2, 7, 14$, which is four factors, and a prime is allowed exactly two.

The same thing happens for any even number bigger than $2$, not just $14$: being even hands it $2$ as an extra factor, on top of the $1$ and itself it already has. That is three distinct factors, one more than a prime is allowed, so the number is composite. Every even number past $2$ fails the same way, which leaves $2$ as the only even prime.

This gives you a fast first filter. If a number bigger than $2$ ends in $0, 2, 4, 6,$ or $8$, you can declare it composite on sight, no division needed. The candidates for “prime” past $2$ are only the odd numbers, and even among those, plenty (like $9$, $15$, $21$) turn out to be composite.

Testing a number by trial division

To decide whether a number $n$ is prime, you hunt for a factor other than $1$ and $n$. Find even one and $n$ is composite; find none and $n$ is prime. The direct method is trial division: try the candidate divisors in turn and watch for a clean division. You do not need to test every number below $n$, and you do not need long division either. That is because the divisibility rules from the last lesson do most of the work.

Test the candidates in increasing order, $2, 3, 5, 7, \ldots$, and lean on the rules you already know:

• Try $2$: is the last digit even? If yes (and $n > 2$), then $n$ is composite.
• Try $3$: does the digit sum come out a multiple of $3$? If yes (and $n > 3$), then $n$ is composite.
• Try $5$: does it end in $0$ or $5$? If yes (and $n > 5$), then $n$ is composite.
• Try $7$, then the next candidates, dividing to check, until either a factor appears or you reach the stopping point in the next section.

You can skip every even candidate after $2$, since an even divisor would make $n$ even and you have already checked $2$. You can also skip multiples of $3$ after $3$, so in practice you test $2, 3, 5, 7, 11, 13, \ldots$, the primes themselves. A few small divisors are enough to settle even a fairly large number. The explanation is the stopping rule, which is the heart of the method.

The stopping rule: when can you quit?

Testing divisors one by one could go on a long time. The key shortcut is that you can stop early: once a candidate divisor $d$ grows large enough that $d \times d$ passes $n$, you are done. If nothing has divided $n$ by the time you reach that point, $n$ is prime. The reason is a fact about how factors come in pairs.

Watch the factors of $36$ do it. They arrive two at a time: $1$ with $36$, $2$ with $18$, $3$ with $12$, $4$ with $9$, and $6$ with $6$. Every one of those pairs has a partner of $6$ or less, and $6$ is the number whose square is $36$. Those six numbers, $1$ through $6$, account for every factor pair $36$ has. A divisor above $6$ could only be the larger partner of a pair you already caught by its smaller one.

In plain terms: keep testing divisors $d = 2, 3, 5, 7, \ldots$ only while $d \times d \le n$. As soon as $d \times d$ passes $n$, stop.

The pairing that $36$ showed you is the whole reason, and it holds for every number. Whenever a number divides $n$, it arrives with a partner: multiply the two and you get $n$ back. One of that pair is never larger than the value whose square is $n$, because two partners both above it would already multiply past $n$. So a search that tries every candidate up to that point, without finding one that divides $n$, has already ruled out every possible pair, and $n$ must be prime.

The Sieve of Eratosthenes

To find all the primes up to some limit at once, there is a method faster than testing each number on its own. That method has been known since antiquity as the Sieve of Eratosthenes (a way to find every prime up to a limit by crossing out multiples). The idea is to start with every number and strain out the composites, leaving the primes behind. A sieve does the same, straining out what you do not want.

Write the whole numbers from $2$ up to your limit. Then repeat one move:

1. Circle the smallest number not yet crossed out. It is prime (nothing below it divided it, or it would already be crossed out).
2. Cross out every larger multiple of that number. They are all composite, since they have it as a factor.

The first prime is $2$, so circle it and cross out $4, 6, 8, 10, \ldots$. The next surviving number is $3$, so circle it and cross out $6, 9, 12, \ldots$. Then $5$, then $7$, and so on. By the stopping rule, once the circled prime times itself passes your limit, everything still standing is prime and you are finished.

Common mistakes