Example 68: Sieve of Eratosthenes

Problem

The sieve of Eratosthenes is the procedure of generating all prime numbers up to a given limit.

Implement a function that generates prime numbers from 1 to 100 using the sieve of Eratosthenes algorithm, which is defined as such:

• Step 1: Fill an array num[ 100 ] with numbers from 1 to 100.
• Step 2: Starting with the second entry in the array, and set all its multiples to zero.
• Step 3: Proceed to the next non-zero element, and set all its multiples to zero.
• Step 4: Repeat step 3 till you have set up the multiples of all non-zero elements to zero.
• Step 5: After step 4, all non-zero entries left in the array would be prime numbers. Print these out.

Example

Input	Output
Nil	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Try it yourself

Try to solve this question on your own in the code widget below. If you get stuck, you can always refer to the solution provided.