We can find prime numbers using a process called the Sieve of Eratosthenes (a dynamic illustration is at Sieve of Eratosthenes - Wikipedia, the free encyclopedia). Eratosthenes (276–195 BC) (Eratosthenes - Wikipedia, the free encyclopedia) was a Greek mathematician who, in addition to developing this process for finding prime numbers, is also credited with being the first to accurately calculate the circumference of the Earth and the distance from the Earth to the sun. He also developed the first map of the world.
Using Eratosthenes' method, we begin by listing every counting number (natural number) greater than 1 up to as big as we want to go. In our example, we will only go up to 29 for now, but a grid for finding all the primes up to 100 is part of this lesson.
The process is a systematic way of circling values we know are prime and crossing out values we know must be composite. For instance, since the set of the only factors of 2 is {1, 2}, the smallest prime must be 2. We circle it. Then we cross out all the other multiples of 2 because those multiples must be composite. We know they must be composite because, in addition to 1 and themselves, they also have 2 as a factor.
Then we move to the next number in the list that is not already crossed out. It is 3. We know that 3 must be prime because the only number in the list less than 3 is 2, and we have already eliminated all the numbers that have 2 as a factor. (Or, the only counting number factors of 3 are 1 and 3.) So we circle 3 and then cross out all multiples of 3. It is alright that some have already been crossed out such as 6. We just need to be sure that all the multiples of 3 have been eliminated from our list.
Now we circle 5 and cross out all the other multiples of 5 in this list that would be 10, 15, 20, and 25, all but 20 are already crossed out.
We circle the 7 and cross out all the multiples of 7. The only other multiples of 7 in the list are 14, 21, and 28 all of which are already crossed out. We circle 11. The only other multiple of 11 on the list is 22 which is already crossed out. We circle 13 and the multiple 26 is already crossed out. In a longer list of numbers, there could be multiples we would need to cross out. The only numbers remaining are 17, 19, 23, and 29, and they have no other multiples in the list either. We circle them.
We now have a list of all the prime numbers that are between 1 and 30. The set of primes between 1 and 30 is {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}.
What did 2 say to the other prime numbers (3, 5, 7, 11, 13, ...)? Answer
Complete the Sieve of Eratosthenes on the following chart.
For the solution with a dynamic illustration seet Sieve of Eratosthenes - Wikipedia, the free encyclopedia.
Content ©2010. All Rights Reserved.
Date last modified: June 24, 2010.
Created with SoftChalk LessonBuilder
By Kris Montis and Timothy Peil
