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.

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

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

« Prev - C Program to Implement Park-Miller Random Number Generation Algorithm

» Next - C Program to Implement Rabin-Miller Primality Test to Check if a Number is Prime

Related Posts:

Recommended Articles: