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.
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;
}
#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.
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.
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
#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.
#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.
#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.
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.
#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
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
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
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.
