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


'ENCRYPTION' 카테고리의 다른 글

machine epsilon  (0) 2018.12.05
C round-off problem  (0) 2018.12.05
Memory Leak And Memory maintenance  (0) 2018.12.03
Sieve of Eratosthenes  (0) 2018.12.03
메르센 소수  (0) 2018.12.03

+ Recent posts