Discover
To find all primes up to 100, Eratosthenes (276–194 BC) had a simple trick. What do you think it was?
- Cross out the multiples of 2, then of 3, of 5, of 7…: what is left is prime
- Test every number by dividing it by all smaller numbers
Key idea
Primes, factors and multiples in history.
- Step 1Euclid c. 300 BCImagined portraitUnknown artist. Public domainAbout 300 BC: Book VII of the Elements and the Euclidean algorithm.
- Step 2Eratosthenes c. 276 – c. 194 BCImagined portraitUnknown artist. Public domainEratosthenes (276–194 BC): the prime number sieve.
Book VII of Euclid's Elements (about 300 BC) is an introduction to number theory and contains the Euclidean algorithm for the greatest common divisor. Eratosthenes of Cyrene (276–194 BC), who also measured the Earth, is remembered for his prime number sieve.
Prime numbers are more than any assigned multitude of prime numbers.
What does Euclid claim here?
- There is no largest prime: the primes never run out
- There are exactly as many primes as he listed
Worked example
Euclid's algorithm for the GCF of 84 and 36.
Practice ★
- What is Eratosthenes remembered for in number theory?
- His prime number sieve
- The algorithm for the GCF
- Negative numbers
- First step of Euclid's algorithm: find the remainder when 42 is divided by 9.
- First step of Euclid's algorithm: find the remainder when 271 is divided by 33.
- Sieve of Eratosthenes on the numbers 1 to 42: after crossing out the multiples of 2 (except 2 itself), how many numbers are left?
Summary card
Primes and factors today
- Online payments are protected by codes built from huge primes.
- Fractions are simplified by dividing by the GCF.
- Calendars and gears repeat after an LCM.
Sources: MacTutor biographies of Euclid and Eratosthenes (see "Sources and credits").