Math : Sieve of Eratosthenes - Finding Prime Numbers

Finding prime numbers

 We can find the prime numbers by using Sieve of Eratosthenes method. (Eratosthenes is a great mathematician who created an efficient method for finding prime numbers)

Let's learn method through example

Example

Find all prime numbers up to 20

 Step 1

Write all the numbers till 15

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

As we know 1 is not a prime number so strike out 1

Step 2

2,3,4,5,6,7,8,9,10,11,12,13,14,15

Here 2 is a prime number and strike out all the numbers which are divisible by 2
(4,6,8,10,12,14 are divisible by 2, so remove all those numbers)
2,3,5,7,9,11,13,15

Step 3

 we should take the next number 3 and proceed like step 2 (9,15 are dvisible by 3, so remove those numbers)
2,3,5,7,11,13

Similarly we should keep going

For our example,
2,3,5,7,11,13 are the prime numbers till 15