Sieve of Eratosthenes
Eratosthenes (whenever I write his name, I can’t stop thinking about a nice and crusty toast) was not only a one-job man: He did not only measure the circumference of Earth, he also contributed to various fields, mathematics in particular. Ancient Greek philosophers dealt with geometry a lot which led to a misunderstanding as if they didn’t work for other branches of mathematics. Reality shows us that lots of Greek philosophers worked for mathematics in a broader aspect. Eratosthenes was one of them and he discovered an ingenious method for finding prime numbers.
Today that method is known as the Sieve of Eratosthenes. This method is really easy to learn and very affective for finding prime numbers in a list. But method is rather slow and takes too much time in larger number lists.
Let me show you how Eratosthenes’ method works between numbers 2 and 100. (I am skipping 1. I’ll be talking about 1 and why it is not considered as prime in another article.)
Thus we start with the number 2, which is the smallest prime number. Here is how the method goes:
- Move in the list until you find a prime number.
- When you find your prime, stop there and square it.
- Go to the square of the prime in the list, and eliminate all the numbers that are multiples of the prime.
- When you finish eliminating, go to your prime in the list and move until you find your next prime number.
- Repeat the same process until there are only primes left in the list.
Example: Let’s do it for 2-100.
2 is prime. Square it: 4. Start eliminating all numbers that are multiples of 2.
Go back to 2. Move to the next number, which is 3. It is prime. Square it: 9. Go to 9 and start eliminating all the numbers that are multiples of 3.
Go back to 3. Move to the next number; 4. It had been eliminated already, thus move to 5 which is a prime number. Square it: 25. Start from 25 and eliminate all the numbers that are multiples of 5.
Go back to 5. Move to the next available number which is 7 and it is a prime number. Square it: 49. Start from 49 and eliminate all the numbers that are multiples of 7.
Go back to 7 and move to the next available number which is 11. It is prime, thus square it: 121. 121 is out of our list. This means every available in our list is a prime number.
New In the Olympics: Walking the Square
Game 1:
- Draw a circle and place eight dots on it.
- You will walk around the circle from the dot that is on top. You’ll take 1 step each time you move, that means you will be moving to the neighbor dot.
- You’d visit every dot with this method until you finish your walk.
Game 2:
- Again start with the same circle and eight dots on it.
- This time you will take 2 steps in each time. That means always move to the second dot.
- When you finish your walk, you’ll see that you visited only half of the dots.
Game 3-4-5-6-7:
Try walking with 3, 4, 5, 6 and 7 steps.
One wonders…
In which steps you would visit all the dots? Do you see anything special about those numbers of steps?
Can you find a general conclusion from this game?
What would you see if you play the same game for 9, 10 and 11 dots?
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 