C Program to Implement Sieve of Eratosthenes to Generate Prime Numbers

«
»
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.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define limit 100 /*size of integers array*/
  5.  
  6. int main(){
  7.     unsigned long long int i,j;
  8.     int *primes;
  9.     int z = 1;
  10.  
  11.     primes = malloc(sizeof(int) * limit);
  12.  
  13.     for (i = 2;i < limit; i++)
  14.         primes[i] = 1;
  15.  
  16.     for (i = 2;i < limit; i++)
  17.         if (primes[i])
  18.             for (j = i;i * j < limit; j++)
  19.                 primes[i * j] = 0;
  20.  
  21.     printf("\nPrime numbers in range 1 to 100 are: \n");
  22.     for (i = 2;i < limit; i++)
  23.         if (primes[i])
  24.             printf("%d\n", i);
  25.  
  26. return 0;
  27. }

advertisement
$ 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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.