C Program To Implement Sieve of Eratosthenes Algorithm
Learn How To Find Prime Numbers using Sieve of Eratosthenes Algorithm in C Programming Language. This code includes a Sieve Method For Prime Numbers in C Language using Array.
This program uses Sieve Function in C that prints all the Prime Numbers within the given range. The Sieve of Eratosthenes Method is a highly efficient algorithm to find Prime Numbers in a given range where the limit can extend upto 1 Million. The Time Complexity for the Sieve Method to Find Prime Numbers in a given range is total time complexity is O(n * log ( log n)).
Example
Prime Numbers Till 10
2 3 5 7
Must Read: C Program To Find Prime Numbers using Normal Method
C Program For Sieve of Eratosthenes Algorithm using Array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <stdio.h> #include <math.h> void sieve_of_erathosthenes(int limit, int temp_arr[]) { int c1, c2; for(c1 = 0; c1 < limit; c1++) { temp_arr[c1] = 1; } temp_arr[0] = 0, temp_arr[1] = 0; for(c1 = 2; c1 < sqrt(limit); c1++) { for(c2 = c1*c1; c2 < limit; c2 = c2 + c1) { temp_arr[c2] = 0; } } } int main() { int limit, count; printf("\nEnter The Limit N To Print Prime Numbers:\t"); scanf("%d", &limit); int temp_arr[limit]; sieve_of_erathosthenes(limit, temp_arr); printf("\n"); for(count = 0; count < limit; count++) { if(temp_arr[count] == 1) { printf("%d\t", count); } } printf("\n"); return 0; } |
Must Read: C Program To Solve Tower of Hanoi Problem without Recursion
Output
If you have any compilation errors or doubts in this Code For Sieve of Eratosthenes Algorithm in C Programming Language, let us know about in the Comment Section below.
Can we not use the simple method to print prime numbers using for loop instead of going for sieve of eratosthenes which is both difficult to pronounce as well as to write?
I agree with you. Using For Loop in the Prime Numbers Program is comparatively easier but this sieve method for printing prime number has advantage with Memory and Execution time which is given more priority in realtime systems.