The Sieve of Eratosthenes

Somewhere in my past I learned about the Sieve of Eratosthenes – it was presented as a method for finding out prime numbers. The end.

In my last reading of Introduction to Arithmetic, Nicomachus mentioned the sieve in Book 1 chapter 13 when talking the relationships between odd numbers, specifically finding out whether any two numbers have a measure in common with one another. We would call this a “common denominator.” Nicomachus says there are three classes of odd numbers, which I won’t go into here because it’s complicated, but he introduces the sieve as a method for producing the three classes, and finding out their “common measure” at the same time. When you mark each odd number as he suggests, their relationships appear.

I stopped at 31 because I was running out of ideas for symbols ;-)

I was taught simply to start with 3 and cross out any number that was divisible by 3, then move to 5 and do the same. This means that you’ll skip over 15 and 45 because they were crossed out when you were doing 3s. Then you do the same with 7, 11, 13, and so on (you skip 9 and all the rest of the numbers you’ve already crossed out). After a while, the numbers you’re left with are the primes – the ones that aren’t divisible by anything other than 1 and themselves.

Doing it Nicomachus’s way is so much richer though, because you’re not just solving a single problem – you’re noticing the relationships between the numbers, and that’s what Arithmetic really is. Not just performing operations with symbols, but understanding the relationships with the reality beyond the symbols.