Eratosthenes sieve program

Here too, its only multiple 14 is already struck out. Iteration 5: 11 is selected. It has no multiples up to Iteration 6: 13 is selected. We just mark 13 as a prime. There are no more numbers left. So, the process stops. We have obtained 2, 3, 5, 7, 11 and 13 as the primes up to The method sieve accepts a parameter n up to which primes are to be calculated. We have a variable num to hold the current number we are considering i.

The while loop has two parts. In the first part, we find all the multiples of num up to n and set primes[multiple] to false. The multiples are found by multiply the number num with 2, 3, 4… in the for loop. Step 2: Starting with the second entry in the array, set all its multiples to zero.

Step 4: Repeat Step 3 till you have set up the multiples of all the non-zero elements to zero. Step 5: At the conclusion of Step 4 , all the non-zero entries left in the array would be prime numbers, so print out these numbers.

Note: Array index starts from 0. So elements from index 0 to 99 will have elements. Here we initialize i to second entry in the array, which has element 2 first prime number. One of the easiest yet efficient methods to generate a list of prime numbers if the Sieve of Eratosthenes link to Wikipedia.

Notice that I use one array to store all the integers, and after I perform the sieve I move the remaining prime numbers into their own array. The program below will store and print the first , primes you can adapt it easily for a larger list if you want.

Another idea is to use a single array, fill it with 1s, and then put 0s on all the numbers that are not primes. The program below prints the first , or so primes using this method:. Because the composite number is not prime. So we can make sure to start with this sequence 2n