#math trivia for #February18: #49 is the first composite that Eratosthenes sieves with a prime other than 2, 3 or 5. What’s the next one?

— Burt Kaliski Jr. (@modulomathy) February 18, 2012

The **Sieve of Eratosthenes** is an ancient algorithm for separating prime numbers from composites. Suppose we want to find all the primes between 1 and 20. The sieve starts with the full sequence of numbers

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .

In the following, we’ll mark primes in *italics* and composites in **bold**. By convention, 1 is neither prime nor composite (it’s a unit), but for convenience, we’ll mark it as composite:

**1** 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .

The sieve follows a simple pattern:

- Let
*p*be the smallest number that’s not yet marked. - Mark
*p*in italics; it must be a prime. - Mark each unmarked multiple of
*p*in bold; it must be composite. - Repeat.

Let’s try this for a few primes. After the 1 is marked, the smallest unmarked number is 2. We’ll mark 2 prime then mark the remaining even numbers composite:

**1** *2* 3 **4** 5 **6** 7 **8** 9 **10** 11 **12** 13 **14** 15 **16** 17 **18** 19 **20** .

The smallest unmarked number is now 3. We’ll mark 3 prime then mark the remaining multiples of 3 composite:

**1** *2* *3* **4** 5 **6** 7 **8** **9** **10** 11 **12** 13 **14** **15** **16** 17 **18** 19 **20** .

The next prime is 5, and the other unmarked numbers in the sequence will also turn out to be prime.

The algorithm is called a “sieve” because it filters out composites, leaving only primes. Any composite by definition has at least one prime divisor smaller then itself. The simple steps above, repeated through the prime *p*, will have filtered out all the composites divisible by primes between 2 and *p*. The next unmarked number must therefore be a prime. And so the process continues.

Any composite that’s not sieved out by 2, 3, and 5 must be divisible by a prime *p* ≥ 7. The smallest composite with this property is 49. The next composite that’s not divisible by at least one of the first three primes — and the **answer to the question** — is the product of the next two primes: **77 = 7*11**.

The next one is 91 = 7*13. So the impact of 2, 3 and 5 is quite extensive: With only two exceptions, every number up to 90 is either divisible by one of the first three primes, or a prime itself.