Day 25 · Jan 25

The Sieve of Eratosthenes

Eratosthenes of Cyrene (276–194 BCE) invented a simple algorithm for finding all prime numbers up to a given limit: write out all numbers, cross out multiples of 2, then multiples of 3, then 5, always starting from the square of the current prime. Every uncrossed number is prime. Eratosthenes also measured the circumference of the Earth with a stick and geometry — getting within 2% of the correct answer — more than 2,000 years before GPS. He was called 'Beta' by his contemporaries — second-best at everything, best at connecting ideas.

Why does the sieve of Eratosthenes only need to check multiples up to the square root of the upper limit?

Practice related topics on DuelMath

Challenge someone →