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
[youtube https://www.youtube.com/watch?v=rb5bClbN3o8]
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
