C Program to Implement Wheel Sieve to Generate Prime Numbers

This is a C Program to find prime number between a given range using Wheel Seive method. Wheel factorization is a graphical method for manually performing a preliminary to the Sieve of Eratosthenes that separates prime numbers from composites.

The algorithm goes this way, Start by writing the natural numbers around circles as shown below. Prime numbers in the innermost circle have their multiples in similar positions as themselves in the other circles, forming spokes of primes and their multiples. Multiples of the prime numbers in the innermost circle form spokes of composite numbers in the outer circles.

Here is source code of the C Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range. 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 <malloc.h>
  3.  
  4. #define MAX_NUM 50
  5. // array will be initialized to 0 being global
  6. int primes[MAX_NUM];
  7.  
  8. void gen_sieve_primes(void) {
  9.     int p;
  10.  
  11.     // mark all multiples of prime selected above as non primes
  12.     int c = 2;
  13.     int mul = p * c;
  14.     for (p = 2; p < MAX_NUM; p++) // for all elements in array
  15.     {
  16.         if (primes[p] == 0) // it is not multiple of any other prime
  17.             primes[p] = 1; // mark it as prime
  18.  
  19.         for (; mul < MAX_NUM;) {
  20.             primes[mul] = -1;
  21.             c++;
  22.             mul = p * c;
  23.         }
  24.     }
  25. }
  26.  
  27. void print_all_primes() {
  28.     int c = 0, i;
  29.     for (i = 0; i < MAX_NUM; i++) {
  30.         if (primes[i] == 1) {
  31.             c++;
  32.  
  33.             if (c < 4) {
  34.                 switch (c) {
  35.                 case 1:
  36.                     printf("%d st prime is: %d\n", c, i);
  37.                     break;
  38.                 case 2:
  39.                     printf("%d nd prime is: %d\n", c, i);
  40.                     break;
  41.                 case 3:
  42.                     printf("%d rd prime is: %d\n", c, i);
  43.                     break;
  44.  
  45.                 default:
  46.                     break;
  47.                 }
  48.             }
  49.  
  50.             else
  51.                 printf("%d th prime is: %d\n", c, i);
  52.         }
  53.     }
  54. }
  55.  
  56. int main() {
  57.     gen_sieve_primes();
  58.     print_all_primes();
  59.     return 0;
  60. }

Output:

$ gcc WheelSeive.c
$ ./a.out
 
1 st prime is: 2
2 nd prime is: 3
3 rd prime is: 5
4 th prime is: 7
5 th prime is: 11
6 th prime is: 13
7 th prime is: 17
8 th prime is: 19
9 th prime is: 23
10 th prime is: 29
11 th prime is: 31
12 th prime is: 37
13 th prime is: 41
14 th prime is: 43
15 th prime is: 47

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.