Implementation of the Sieve of Eratosthenes in C

To get started, we go through each number from 2 onwards marking off its multiples as composite numbers (not prime). This is repeated for every prime found.

Algorithm

1. To start, make a list of prime[] having n+1 indices with each having true, where true represents the index has a prime number.
    
2. Since 0 and 1 are not prime numbers, set prime[0] and prime[1] to false.
    
3. Starting from 2, for i=2, is i contained in prime[]? If yes, then proceed: true means it is a prime number otherwise it is not so skip all other steps that follows and move to the next i. After that go through all multiples of i (like i*i, i*i+i, i*i+2i,…) such that each multiple is less than or equal to n and make them false in the list.
    
4. Similarly find all multiples which are less than or equal to n and set them false in prime[] array.
    
5. Do the above process until you reach sqrt(n). Any index that is still marked as true in the list, shows that number is a prime one.

The above method is not only easy but it also works very efficiently especially when you want to find all prime numbers below any given maximum limit

The Sieve of Eratosthenes is a simple and efficient algorithm for finding all prime numbers up to a specified integer. It was created by the ancient Greek mathematician Eratosthenes and is still used today due to its efficiency when dealing with large numbers.

In this article, we will learn how to implement sieve of Eratosthenes in C.