What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is a method for determining all prime numbers up to any given number.
The word "sieve" refers to a tool that serves to separate different components of a mixture, retaining the larger ones and allowing smaller substances to pass through.
The Sieve of Eratosthenes is an algorithm that separates the prime numbers from the non-prime numbers (that is, the number one and the composite numbers).
In the next applet you may apply this method to determine all prime numbers up to a given limit. You only need to follow all steps in it.
- Choose the number of columns and the number of rows.
- You may disable the Sound option (which is on by default).
- Then all you have to do is to follow all the instructions. At the end a "Restart" button appears. Clicking it you may choose the numbers of columns and rows and start the algorithm again.
Try to follow all the steps without seeing what follows next. In case a step is unclear, you may consult some explanations about how the method works here.
This method is quite efficient for determining all prime numbers less than a certain value, because it involves only multiplications (in the choice of the multiples of a prime) and, in general, it seems easier to multiply than to divide.
Note that, however, to test whether a given natural number is prime, it is not necessary to apply the Eratosthenes sieve; it suffices to check whether it is divisible by some prime number \(p\) whose product \(p\times p\) does not exceed the given number (before moving on, think of a possible reason for this statement).
In fact, as we saw in question II, the first composite number that admits a prime number \(p\) as its least divisor (other than \(1\)) is \(p \times p\). In other words, any composite number less than \(p \times p\) must have a prime divisor less than \(p\).
Hence, we may conclude that, given a natural number \(n\) bigger than \(1\), if \(n\) is not divisible by any prime \(p\) such that \(p \times p\leq n\), then \(n\) is prime.
