Sieve of Eratosthenes by Deepika

The Sieve of Eratosthenes is the first known algorithm for generating prime numbers. It can be used to test if a number is prime, or to find all the prime numbers less than or equal to a number. It works by eliminating all the composite numbers less than or equal to the number. 


The first step in the algorithm is to list all the natural numbers from two up to and including the number being tested (n). Next, starting at the beginning of the list, find the first number that is not crossed out, and cross out all of its multiples. After this, proceed to the next number that is not crossed out and cross out its multiples. Repeat this process until you reach the square root of the number you are examining. Any number that is not crossed out at the end is prime. The algorithm is best explained with an example

credits :http://banach.millersville.edu/~bob/math478/History/sieve.html