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

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

prime numbers from 2 to 100 sieve of erathosthenes

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


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

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

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

Designated Initializers In Array: C Program

In this video tutorial lets learn about Designated Initializers in arrays.

C99 introduced the concept of designated initializers. These allow you to specify which elements of an array, structure or union are to be initialized by the values following.

We’ll look at using Designated Initializers for structures and unions in separate video tutorial, for now lets see how we can use it for arrays in C programming language.

Related Read:
Basics of Arrays: C Program

Where should we use Designated Initializers?

When you have a very large array and most of the elements of array are zeros and only couple of elements are non-zeros. In that case, you can use designators to initialize particular elements of an array to non-zero values.

Video Tutorial: Designated Initializers In Array: C Program


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

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

Source Code: Designated Initializers In Array: C Program

1. Display array Elements

#include<stdio.h>

int main()
{
    int a[5] = {0, 0, 1, 0, 8}, i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
1
0
8

We use simple for loop to loop through all the elements of an array and display it on to the console window.

2. Garbage values inside uninitialized array

#include<stdio.h>

int main()
{
    int a[5], i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
6356864
4200750
4200656
46
8

If array elements are not initialized it’ll have garbage values. Even if you initialize one element in that array, the rest of the elements will be automatically initialized to zero. And even if you simply have a equal sign and opening and closing curly braces in front of array variable, the compiler will assign zero to all the elements.

3. All zeros as array element

#include<stdio.h>

int main()
{
    int a[5] = {}, i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
0
0
0

Since we’ve opening and closing flower bracket or curly brackets in front of array declaration, compiler will automatically assign zeros as array elements.

4. Overwrite the values of array element

#include<stdio.h>

int main()
{
    int a[5], i;

    a[2] = 1;
    a[4] = 8;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
6356864
4200766
1
46
8

From source code 2 above, we know that uninitialized arrays will have garbage values inside it. We are over-writing the garbage values at index 2 and index 4 with 1 and 8 respectively. So except for index 2 and 4 all other spots are filled with garbage values.

5. Overwrite the zeros in array

#include<stdio.h>

int main()
{
    // {0, 0, 1, 0, 8}
    int a[5] = {}, i;

    a[2] = 1;
    a[4] = 8;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
1
0
8

So this fixes our issue. Since we’ve empty opening and closing curly braces after declaring array variable, all the elements of array will be automatically initialized to 0.

After that we overwrite the values at index 2 and 4 with 1 and 8.

Now lets make use of Designated Initializers

For arrays with large size we need to use Designated Initializers. Because we can’t individually assign values by overwriting it. It’ll take lot of space in your source code. To avoid that, and to write it in single line of code, we make use of Designated Initializers.

6. Designated Initializers in array

#include<stdio.h>

int main()
{
    // {0, 0, 1, 0, 8}
    int a[5] = {[2] = 1, [4] = 8}, i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
1
0
8

Here we initialized values of index 2 and 4 to 1 and 8 respectively in a single line of code. Here [2] and [4] are called Designators.

7. Designated Initializers: order of index appearance doesn’t matter

#include<stdio.h>

int main()
{
    // {0, 0, 1, 0, 8}
    int a[5] = {[4] = 8, [2] = 1}, i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
1
0
8

As you can see the designator [4] appears before the designator [2], but still it doesn’t change anything with the output.

8. Designated Initializers: Alternate Syntax

#include<stdio.h>

int main()
{
    // {0, 0, 1, 0, 8}
    int a[5] = {[2]1, [4]8}, i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
1
0
8

As you can see in above source code, we are not using equal sign(=) to assign value to designators. And it’s valid syntax.

9. Designated Initializers: Mixed Syntax

#include<stdio.h>

int main()
{
    // {0, 0, 1, 0, 8}
    int a[5] = {[2]1, [4] = 8}, i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
1
0
8

You can see that we’ve used both syntax to initialize value to particular index of the array. i.e., [2]1 and [4] = 8. Even if we mix both these syntax, it works and its perfectly valid syntax in C standard.

10. Designated Initializers: And dynamic array size

#include<stdio.h>

int main()
{
    // {0, 0, 1, 0, 8, 0, 0, 0, 0, 0, 5}
    int a[] = {[2]1, [4] = 8, [10] = 5}, i;

    for(i = 0; i < 11; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
0
1
0
8
0
0
0
0
0
5

If we don’t mention length or size of the array explicitly, then the compiler will assign the length or size of the array from the largest designator in the list.

Note: Since the largest designator is 10 in above source code, which must be N – 1 i.e, 11 – 1 = 10. So array size is 11. OR since index starts from 0, and the largest designator is 10. i.e., 0 to 10, which means 11 elements in an array.

11. Designated Initializers: Designators and normal initializers

#include<stdio.h>

int main()
{
    // {4, 6, 1, 0, 8}
    int a[5] = {4, 6, [2]1, [4] = 8}, i;

    for(i = 0; i < 5; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
4
6
1
0
8

Here we’ve intialized index 0 to 1, index 1 to 6, and then we’re using designators to initialize index 2 to value 1 and index 4 to value 8.

12. Designated Initializers: initialize range of elements in an array

#include<stdio.h>


int main()
{
    // {0, 2, 2, 2, 3, 3, 3, 0, 0, 0}
    int a[10] = {[1 ... 3] = 2, [4 ... 6] = 3}, i;

    for(i = 0; i < 10; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
2
2
2
3
3
3
0
0
0

Here we make use of designators to initialize range of elements. Syntax is [first … last] = value. i.e., the first index to start initializing and the last index to end the initialization. In between these two indexes there are 3 dots.

13. Designated Initializers: initialize range of elements in an array, with mixed syntax

#include<stdio.h>

int main()
{
    // { 0, 2, 2, 2, 3, 3, 3, 5, 0, 0}
    int a[10] = {[1 ... 3] = 2, [4 ... 6]3, 5}, i;

    for(i = 0; i < 10; i++)
        printf("%d\n", a[i]);

    return 0;
}

Output:
0
2
2
2
3
3
3
5
0
0

In above source code you can see mixed syntax to initialize elements of the array. i.e., [1 … 3] = 2 is valid, [4 … 6]3 is valid too, and index 7 is assigned a value of 5 directly. All other indexes will have a value of zero.

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