Prime Numbers : Sieve Of Eratosthenes

                Prime Number is the number which can be divided by only itself and 1. To determine whether a number is prime or not, we must ensure that number is not divisible by any number between 1 and number itself. Suppose we have to determine whether N is prime or not. For that we have to check divisibility of N for 2 to (N-1).

                If we want prime numbers up to N, the same procedure can be repeated for N numbers. Can we do it better? yes, that’s reason for Writing this post. Algorithm called “Sieve of Eratosthenes” find all the prime numbers up to N more efficiently than former method.

                For the understanding method of Eratosthenes, let’s take an example of finding Prime numbers up to 20.

                2: Prime Number

                                So , multiples of 2 : {4,6,8,10,12,14,16,18,20}

                                        Cannot be prime because they can be divided by 2.

                3: Prime Number

                                So, multiples of 3 : {6,9,12,15,18}

                                       Cannot be prime, They can be divided  by 3.

                .

                . // so on …

                .

                PrimeNumersUpTo (20) = {2,3,5,7,11,13,17,19}

                When one number is prime number its all multiples cannot be the prime number, Because all multiples of any number can be divided by the number. This principle is applied in the “Sieve Of Eratosthenes”. When we have to find all prime up to N, We can start with 2 and mark all the multiples of 2 as non-primes. Then remaining numbers to be checked, we take the minimum and make all the multiples of that number as non-primes. At the end, we have prime numbers up to N.

                If we look at the divisible of any number, we can say that numbers are repeated after its root. Like 36...

                2 x 18 = 36

                3 x 12 = 36

                4 x   9 = 36

                6 x   6 = 36

                                NOW .. 9 x 4 = 36 , But 9 and 4 are already encounteres as divisible at 4 x 9 = 36.

                With the help of above fact, we have to only up to square root of N because all the multiples of N already checked till its square root.

C++ Code for Implementation of “Sieve Of Eratosthenes”.