This C program is used to implement Sieve of Eratosthenes to generate prime numbers between given range. The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer. Implement this algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn’t optimize by using pre-computed wheels, i.e. don’t assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.
Here is the source code of the C program to generate prime numbers. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
#include <stdio.h>
#include <stdlib.h>
#define limit 100 /*size of integers array*/
int main(){
unsigned long long int i,j;
int *primes;
int z = 1;
primes = malloc(sizeof(int) * limit);
for (i = 2;i < limit; i++)
primes[i] = 1;
for (i = 2;i < limit; i++)
if (primes[i])
for (j = i;i * j < limit; j++)
primes[i * j] = 0;
printf("\nPrime numbers in range 1 to 100 are: \n");
for (i = 2;i < limit; i++)
if (primes[i])
printf("%d\n", i);
return 0;
}
$ gcc prime.c -o prime $ ./prime Prime numbers in range 1 to 100 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Next Steps:
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Buy C Books
- Practice Computer Science MCQs
- Watch Advanced C Programming Videos
- Apply for Computer Science Internship
- Apply for C Internship