Sieve of Eratosthenes
Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.
The algorithm is based on following idea: prime number has just two natural divisors: 1 and itself.
It means that non-prime numbers are multiples of other natural number.
If we want to find prime numbers from 1 to 100, we write a sequence of numbers and we erase multiples of 2, 3 etc. Remaining numbers are prime numbers.
To program the algorithm, we have an array of integers or boolean values. The array item A[i] is equal to 1, if i
is a prime number, otherwise it is set to zero. Firstly, all array item are set to 1 (we suppose all numbers are prime numbers).
Then, array items with indecec of multiples 2, 3 , ... , are set to 0 in loop.
If some A[j]=0, multiples of j were already set to 0.
We print indices of items that are set to 0 at the end.