What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes decants composite numbers, leaving behind the prime numbers.
A prime number is a positive integer, whose factors are 1 and the number itself. A prime number will always allow only 2 factors.
Let's see how Eratosthenes's sieve works:
We'll write rows with numbers from 1 to 10, 10 to 20,...90 to 100.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
91 92 93 94 95 96 97 98 99 100
Since 1 is not a prime, we'll take 2 as the first even prime number and then we'll cross out each multiple of 2.
We'll take 3 as the next positive integer prime and we'll cross out it's multiples. Some of the number are already crossed out, since they were the multiples of the prime 2, also.
We'll take the next number, namely 5 and we'll cross out the multiples of 5.
We'll continue to do that until we'll finish all the numbers up to 100. The crossed out numbers are the multiples, the open numbers being the primes.
The Sieve of Eratosthenes is a way of finding prime numbers lower than any given number. The process is simple though it does take a lot of time, especially if the number till which we have to find the prime numbers is large. To describe the method let’s assume you want to find all the prime numbers between 1 and N. The method works like this:
First determine the square root ‘S’ of the perfect square equal to or just larger than N. Now draw 10 columns. Start writing numbers row-wise, starting from 1, moving on to the next row once you are done with 10 numbers. After all the numbers from 1 to N have been written, you begin a process of elimination. Encircle the first prime number which is 2, and cross out all the multiples of 2 that follow. Once this is done, move to the next number that has not been crossed out, that would be 3. Encircle it and cross out all multiples of 3 in the table. Similarly continue, by encircling the number that is not crossed out and crossing out all further multiples of that number. You would have to do this only for the first S numbers, as that will cover the entire table. Once you are done, all the prime numbers in the table will be encircled and the other numbers crossed out.
The Sieve of Eratosthenes hence is a method that allows us to identify prime numbers in a relatively easy way.