Advertisement
Paul_Pedant

Sieve Primes in C

Jun 11th, 2020
405
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.38 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. int main ()
  6.  
  7. {
  8.     int i, j, x;
  9.     char *sieve = NULL;
  10.     int  *primes = NULL;
  11.    
  12.     printf("\nInput highest number: ");
  13.     scanf ("%d", & x);
  14.  
  15.     // X is our input and size is now x.
  16.     sieve = malloc (sizeof (*sieve) * x);
  17.     printf ("Debug: sieve is %p\n", sieve);
  18.    
  19.     for (i = 2; i < x; i++) {  
  20.         sieve[i] = 1;
  21.     }      
  22.     for (i = 2; i < sqrt (x); i++) {  
  23.         if (sieve[i] == 1){
  24.             for (j =i; i * j < x; j++) {
  25.                 sieve[i * j] = 0;
  26.             }                  
  27.         }                      
  28.     }
  29.     // Print out what the sieve contains.
  30.     for (i = 2, j = 0; i < x; i++) {
  31.         if (sieve[i]) {
  32.             printf ("%3d. Prime number = %d\n", ++j, i);
  33.         }      
  34.     }
  35.     // Fetch primes from the sieve into a compact array.
  36.     for (i = 2, j = 0; i < x; i++) {
  37.         if (sieve[i]) {
  38.             primes = realloc (primes, ++j * sizeof (*primes));
  39.             primes [j - 1] = i;
  40.         }      
  41.     }
  42.     printf ("Debug: primes is %p\n", primes);
  43.  
  44.     // Print out the list of primes.
  45.     for (i = 0; i < j; i++) {
  46.         printf ("%3d. Prime number = %d\n", i + 1, primes[i]);
  47.     }
  48.     primes = realloc (primes, (size_t) 0);
  49.     printf ("Debug: primes is %p\n", primes);
  50.     free (sieve);
  51.  
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement