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

```\$ 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 