Name: Lynn

Who is asking: Parent
Level: Middle

Question:
My daughter has been asked to find all the prime numbers by using the Sieve of Eratosthenes. I have no understanding what this means.

No one knows an efficient way to generate the primes. This is a problem that has challenged mathematicians for more than 2000 years. There are an infinite number of primes so "listing" them all would be impossible. We don't even know an efficient way to tell if a large number is a prime or not, say a number with 200 digits. About 200 B.C. Eratosthenes gave us a primitive method to find all the primes up to some number, for example all the primes up to 100. His procedure is called the Sieve of Erathosthenes. I am going to illustrate it by finding all the primes up to 100.

List the numbers from 2 to 100.

• We know 2 is a prime. Circle it and cross out all the remaining multiples of 2;
  
  
  
• the least number remaining, 3, is then prime. Circle it and cross out all the remaining multiples of 3;
  
  
  
• the least number remaining, 5, is then prime. Circle it and cross out all the remaining multiples of 5
  
• and now 7
  

Of course this is a tedious method to determine primes, and many sophisticated algorithms have been developed in efforts to determine whether or not any given number is prime. Such information is not important solely for academic reasons but has very important applications in encryption codes used by banks, credit card companies, and Internet shops.

The largest prime known has about one million digits, but even though we know that there are primes with ten million digits, none is currently known. (See http://www.utm.edu/research/primes/largest.html for more details.)