Tag: Sieve

Lets write a C program to find prime numbers from 2 to N, using Sieve of Eratosthenes method.

Important Note

We are working on index numbers here. Array elements will have only 2 values: 1 or 0. Wherever the value of array element is 1, that means it’s position/index number is prime orelse its composite number.

Working on array elements

This video tutorial solves text book problem statement to find prime numbers using Sieve of Eratosthenes Method: Prime Numbers using Sieve of Eratosthenes: C Program.

Visual Representation

Video Tutorial: Sieve of Eratosthenes Method To Find Prime Numbers: C Program

Source Code: Find Prime Numbers from 2 To N using Sieve of Eratosthenes: C Program

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

#define N 101

int main()
{
    int a[N] = {[0 ... N - 1] = 1}, i, j;
    int num  = sqrt(N - 1);

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

    printf("Sieve of Eratosthenes\n");
    printf("Prime numbers from 2 to %d are ...\n", N - 1);
    for(i = 2; i < N; i++)
    {
        if(a[i])
            printf("%d\t", i);
    }

    return 0;
}

Output
Above code outputs all the prime numbers between 2 to N – 1.

Logic To Find Prime Numbers from 2 To N using Sieve of Eratosthenes

1. We’re using Designated Initializers to initialize all the elements of array to 1. Here we are initializing all the elements from index 0 to N – 1. If you write 0 to N, it’ll start throwing out of bounds error. As 0 to 101(if N value is 101) will be 102 elements, which exceeds the size of array.

2. Next we find square root of N – 1. Its enough to check till square root of N – 1, to get all the prime numbers – I’ve shown you the proof in the video posted above in this article.

3. Since 2 is the first prime number, we initialize i to 2 and we iterate the for loop till square root of N – 1. For each iteration increment the value of i by 1.

4. Initially we assume that all the numbers are prime, by storing 1 in all the array elements.

5. After careful observation, we come to know that the first index position we store zero for any index i is i * i. So we initialize j value to i * i. For each iteration of the inner for loop we increment the value of j by i times. Inside inner for loop we store 0 at a[j].

If we keep adding value of i to the previous value of j, then j will always have a number which is multiple of i. So we store 0 at a[j].

6. We keep repeating Step 5 until i is less than or equal to square root of N – 1.

7. Once i is equal to square root of N – 1, we print all the index numbers or position of element which has 1 in it. So these index numbers are prime numbers from 2 to N – 1.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert