Sieve Of Eratosthenes (C++)

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer.

The Algorithm:
1. Create a contiguous list of numbers from two to some highest number n.
2. Strike out from the list all multiples of two (4, 6, 8 etc.).
3. The list's next number that has not been struck out is a prime number.
4. Strike out from the list all multiples of the number you identified in the previous step.
5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
6. All the remaining numbers in the list are prime.

The C++ code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include "stdio.h" #include "conio.h" const int SIZE = 10000; char f[SIZE + 1]; int main() { // 0 and 1 is not prime f[0]=f[1]=1; // every even number (except 2) is not prime for(int i=4;i<=SIZE;i+=2) f[i]=1; // iterate every odd number (start from 3) for(int i=3;i*i<=SIZE;i+=2) { // if the current number is prime then the multiple is not prime if(f[i]==0) { for(int j=i*i;j<=SIZE;j+=i) f[j]=1; } } // display prime numbers between 0 and 100 for(int i=0;i<=100;i++) if(f[i]==0) printf("%d\n",i); getch(); return 0; }