Testing Primes and the Sieve of Eratosthenes

You met primes in grade 4. Now we need a precise definition and two dependable tools: a test for one number and a way to list all primes up to a bound.

Definitions. An integer $p > 1$ is prime when its only positive divisors are $1$ and $p$. An integer $n > 1$ that is not prime is composite: it can be written $n = ab$ with $1 < a, b < n$. The number $1$ is neither. (Leaving $1$ out is what keeps prime factorizations unique; otherwise $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3$.)

Why it works

You only need to test up to $\sqrt{n}$. Suppose $n = ab$ with $1 < a \le b$. Then $a \cdot a \le a \cdot b = n$, so $a \le \sqrt{n}$. The smallest prime factor of $a$ is at most $a$ and also divides $n$. So a composite $n$ always has a prime factor at most $\sqrt{n}$. Turn that around: if no prime up to $\sqrt{n}$ divides $n$, then $n$ is prime.

Worked example: A composite in disguise

Is $221$ prime?

$14^{2} = 196$ and $15^{2} = 225$, so $\sqrt{221} \approx 14.9$. Test the primes $2, 3, 5, 7, 11, 13$.
$221$ is odd, its digit sum is $5$ (not a multiple of 3), and it does not end in $0$ or $5$. $221 = 7 \cdot 31 + 4$ and $221 = 11 \cdot 20 + 1$.
$221 = 13 \cdot 17$. Composite.

Answer: No: $221 = 13 \cdot 17$.

Worked example: A prime

Is $211$ prime?

$\sqrt{211} \approx 14.5$, so test $2, 3, 5, 7, 11, 13$.
The remainders are $1, 1, 1, 1, 2, 3$. None is $0$.
No prime up to $\sqrt{211}$ divides $211$, so it is prime.

Answer: Yes.

The sieve of Eratosthenes

To list every prime up to $N$: write $2, 3, \dots, N$. Circle the smallest number not yet crossed out; it is prime. Cross out its multiples, starting at its square. Repeat. Once the next circled number $p$ has $p^{2} > N$, everything still standing is prime.

Crossing out starts at $p^{2}$: a smaller multiple $kp$ with $k < p$ has a prime factor smaller than $p$, so it is already crossed out. After 7, the next prime is 11, and $11^{2} = 121 > 100$.

Worked example: How far does the sieve go?

To list the primes up to $200$ with the sieve, which primes do you need to sieve with?

You need the primes $p$ with $p^{2} \le 200$.
$13^{2} = 169 \le 200$ but $17^{2} = 289 > 200$.
So sieve with $2, 3, 5, 7, 11, 13$. Every number left after that is prime.

Answer: $2, 3, 5, 7, 11$ and $13$.

Common mistake

Testing every number up to $n$ (slow, though correct), or stopping too early. Stopping at $11$ for $221$ would call it prime, but $13 \le \sqrt{221}$ still had to be tried. Find the whole-number part of $\sqrt{n}$ first and test every prime up to it. And remember: $1$ is not prime.

Key idea

A composite $n$ has a prime factor $p \le \sqrt{n}$. So test the primes up to $\sqrt{n}$; to list all primes up to $N$, sieve with the primes up to $\sqrt{N}$.

Testing Primes and the Sieve of Eratosthenes

The sieve of Eratosthenes

Practice

Builds on

Leads to

Sources and further reading