Implementing Sieve Of Eratosthenes - Finding Prime Numbers - C Program (Procedural)

Problem Question

Write a program to implement Sieve of Eratosthenes.

Explanation of Problem

Sieve of Eratosthenes is a simple algorithm which is used to find prime numbers easily and in a quick way. As compared to traditional way where we divide each number with every number before them to check if they are prime or not, sieve of Eratosthenes removes all mulitples of a number as it progresses forward, thus eliminating the need of a lot of extra comparisons. Hence the algorithm makes it very efficient to find prime numbers.
To implement the sieve of Eratosthenes, we would follow the following steps.
Step one: Fill and array with numbers 1 to n.
Step two: Starting with the number "2", set all its multiples to zero.
Step three: Proceed to the next non-zero element and set all its multiples to zero.
Step four: Repeat step three until all the multiples of all the non zero elements are set to zero.
Step five: At the conclusion of step four, all the non zero entries left in the array would be prime numbers; so print out these numbers.
As you can see in this algorithm the way prime numbers are derived, is far easier and incurs less amount of time as compared to the traditional way how we check if a number is prime or not where in, we would loop through all the numbers until that number and Keep checking if any of those numbers is full divisor of that number, which we are checking to be prime or not. What we are doing in this implementation is that we end up removing all the entries which are multiples of a number in each pass, for example when we are working with the number 2 we remove all its multiples in the first pass of the list itself so we are not going to check all the Even Numbers again and again for all the numbers before that, to check whether or not they have a full divisor or not. Hence, this algorithm saves some time, and in the end we have some elements which are non zero which represent the prime numbers and some elements which are zero which represent the non prime numbers. The prime numbers are left above the sieve as non-zero and the numbers which are non Prime get out of the sieve as zeroes.

Refer the following example to better understand how it works.

The implementation is fairly simple so let's dive into the code. 

Code

#include <stdio.h>
/**@Title: SieveOfEratosthenes.c*
*@Language: ANSI C*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Toxifier*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-06-2015*
*/

#include <stdio.h>
int main()
{
    int userInput, outerLoop, innerLoop, numberList[10000];
    printf ("Welcome to SieveOfEratosthenes\n");
    printf ("Made by Toxifier\n");

    printf ("Enter the number upto which to find prime numbers (upto 9999): ");
    scanf ("%d", &userInput);

    for (outerLoop = 0; outerLoop < userInput; outerLoop++)
    {
        numberList[outerLoop] = outerLoop;
    }

    for (outerLoop = 2; outerLoop * outerLoop <= userInput; outerLoop++)
    {
        if (numberList[outerLoop] != 0)
        {
            for (innerLoop = outerLoop * outerLoop; innerLoop <= userInput; innerLoop = innerLoop + outerLoop)
            {
                numberList[innerLoop] = 0;
            }
        }
    }

    for (outerLoop = 2; outerLoop <= userInput; outerLoop++)
    {
        if (numberList[outerLoop] != 0)
        {
            printf("%d ", numberList[outerLoop]);
        }
    }

    printf ("\nThank You for using SieveOfEratosthenes\n");
    printf ("Made by Toxifier\n");
    system("pause");
    return 0;
}

Explanation of Code

#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.

scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.

int userInput, outerLoop, innerLoop, numberList[10000]; -> Here we define the variables we are going to use in our program.
outerLoop and innerLoop are the loop variables.
userInput is used to gather user input. It defines the number upto which you want the program to find prime numbers. numberList[10000] is the array which will hold the numbers, and be worked upon to have only prime numbers in the end.

    for (outerLoop = 0; outerLoop < userInput; outerLoop++)
    {
        numberList[outerLoop] = outerLoop;
    }

Here we setup our array with all numbers upto the user input.

for (outerLoop = 2; outerLoop * outerLoop <= userInput; outerLoop++)
    {
        if (numberList[outerLoop] != 0)
        {
            for (innerLoop = outerLoop * outerLoop; innerLoop <= userInput; innerLoop = innerLoop + outerLoop)
            {
                numberList[innerLoop] = 0;
            }
        }
    }

Here we implement the Sieve of Eratosthenes algorithm. We start with number 2 and go upto the high value entered by user. We then mark all multiple of that number as 0. Looking at the loop, you'd notice that the inner loop starts from outerLoop * outerLoop. This is because all the multiples prior to that value are already removed by the previos iteration. For exmaple, when the loop works for number 2, it removes all even numbers. Hence, for 3, we dont need to consider 6 and start with 9 directly. Similarly, for 5, 10 and 20 are removed by 2 and 15 by 3, hence we directly start with 25. And so on.

for (outerLoop = 2; outerLoop <= userInput; outerLoop++)
    {
        if (numberList[outerLoop] != 0)
        {
            printf("%d ", numberList[outerLoop]);
        }
    }

Here we print the remaining values on the sieve, all non zero values from 2 onwards. This is the list of prime numbers.




printf ("Thank You for using SieveOfEratosthenes\n");
            printf ("Made by Toxifier\n");
Here we just print a goodbye message for user before exiting the program :)

system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)

Download Source Code