Prime Numbers using Sieve of Eratosthenes: C Program

Implement in a c program the following procedure to generate prime numbers from 1 to 100. This procedure is called Sieve of Eratosthenes.

Step 1: Fill an array num[100] with numbers from 1 to 100.

Step 2: Starting with the second entry in the array, 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 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.

Page Contents

Simpler Version of Sieve of Eratosthenes

You can watch our previous video tutorial for simpler version of Sieve of Eratosthenes method to find prime numbers from 2 to N: Find Prime Numbers from 2 To N using Sieve of Eratosthenes: C Program.

Visual Representation

prime numbers from 2 to 100 sieve of erathosthenes

Video Tutorial: Prime Numbers using Sieve of Eratosthenes: C Program

[youtube https://www.youtube.com/watch?v=oL9jzKm6uZQ]

YouTube Link: https://www.youtube.com/watch?v=oL9jzKm6uZQ [Watch the Video In Full Screen.]

Input num[N] with numbers 1 to 100

Step 1:

#include<stdio.h>

#define N 100

int main()
{
    int num[N], i;

    for(i = 0; i < N; i++)
        num[i] = i + 1;

    for(i = 0; i < N; i++)
            printf("%d\t", num[i]);

    return 0;
}

Output:
This code outputs natural numbers from 1 to 100.

Note:
Array index starts from 0. So elements from index 0 to 99 will have 100 elements.

At index 0 we’ll store number 1, and at index 1 we’ll store number 2 and so on until index 99 where we store number 100. i.e., the index number is 1 less than the element/number present at that index.

Starting with the second entry in the array, set all its multiples to zero.

Step 2:

    int limit = sqrt(N);

    for(i = 1; i <= limit; i++)
    {
        if(num[i] != 0)
        {
            for(j = pow(num[i], 2); j <= N; j = j + num[i])
            {
                num[j - 1] = 0;
            }
        }

    }

Here we initialize i to second entry in the array, which has element 2(first prime number). Iterate the for loop until i is less than or equal to square root of N or you can even write (num[i] * num[i]) <= N as the condition for outer for loop. We’ve shown the reason for writing that condition in our other video tutorial present here: Find Prime Numbers from 2 To N using Sieve of Eratosthenes: C Program.

Step 3: Proceed to the next non-zero element and set all its multiples to zero.

Inside inner for loop: for any non-zero element we check for their multiples and if we find any, we store 0 – indicating that it was a composite number.

We repeat Step 3 till we have set up the multiples of all the non-zero elements to zero.

Initialized j to pow(num[i], 2) ?

Because the first number to be struck off by num[i] will be pow(num[i], 2) or (num[i] x num[i]). In other words, the first number or the first multiple of num[i] where our program will insert 0 is pow(num[i], 2) or (num[i] x num[i]).

j = j + num[i]
It can also be written as j += num[i]. For each iteration of inner for loop, j value should increment by num[i] times, so that the position (j – 1) will have the multiple of number present at num[i]. In that case num[j – 1] will be multiple of num[i], and hence composite number – so we store 0 at num[j – 1].

Step 5: Print Prime Numbers
Finally all the non-zero numbers/elements are prime numbers.

Source Code: Prime Numbers using Sieve of Eratosthenes: C Program

using math.h library file

#include<stdio.h>
#include<math.h>

#define N 100

int main()
{
    int num[N], i, j;
    int limit = sqrt(N);

    for(i = 0; i < N; i++)
        num[i] = i + 1;

    for(i = 1; i <= limit; i++)
    {
        if(num[i] != 0)
        {
            for(j = pow(num[i], 2); j <= N; j = j + num[i])
            {
                num[j - 1] = 0;
            }
        }

    }

    printf("Sieve of Eratosthenes Method\n");
    printf("To find Prime numbers from 2 to %d\n\n", N);
    for(i = 1; i < N; i++)
    {
        if(num[i] != 0)
            printf("%d\t", num[i]);
    }

    printf("\n");

    return 0;
}

Output
This outputs all the prime numbers from 2 to 100.

Source Code: Without using math.h library file

#include<stdio.h>

#define N 100

int main()
{
    int num[N], i, j;

    for(i = 0; i < N; i++)
        num[i] = i + 1;

    for(i = 1; (num[i] * num[i]) <= N; i++)
    {
        if(num[i] != 0)
        {
            for(j = num[i] * num[i]; j <= N; j += num[i])
            {
                num[j - 1] = 0;
            }
        }

    }

    printf("Sieve of Eratosthenes Method\n");
    printf("To find Prime numbers from 2 to %d\n\n", N);
    for(i = 1; i < N; i++)
    {
        if(num[i] != 0)
            printf("%d\t", num[i]);
    }

    printf("\n");

    return 0;
}