home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Professional / OS2PRO194.ISO / os2 / prgramer / unix / emx / test / sieve.c < prev    next >
C/C++ Source or Header  |  1992-11-23  |  2KB  |  113 lines
  1. /* sieve.c (emx+gcc) */
  2.  
  3. /* Define BITS to use bit encoding instead of byte encoding */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <memory.h>
  8.  
  9. #define FALSE   0
  10. #define TRUE    1
  11.  
  12. #define N(x) ((x)/3)
  13.  
  14. typedef unsigned long ULONG;
  15. typedef unsigned char BYTE;
  16.  
  17. #if defined (BITS)
  18.  
  19. #define index(c) ((c)>>3)
  20. #define mask(c)  (1<<((c)&0x07))
  21. #define BIT_ON(map,c) (map[index(c)] & mask(c))
  22. #define BIT_OFF(map,c) (!BIT_ON(map,c))
  23. #define SET_TRUE(map,c) map[index(c)] |= mask(c)
  24. #define SET_FALSE(map,c) map[index(c)] &= ~mask(c)
  25. #define BYTES(s) (((s)+7)>>3)
  26.  
  27. #else
  28.  
  29. #define BIT_ON(map,c) map[c]
  30. #define BIT_OFF(map,c) !map[c]
  31. #define SET_TRUE(map,c) map[c] = 1
  32. #define SET_FALSE(map,c) map[c] = 0
  33. #define BYTES(s) (s)
  34.  
  35. #endif
  36.  
  37. static ULONG isqrt (ULONG x);
  38. static void usage (void);
  39.  
  40.  
  41. static ULONG isqrt (ULONG x)
  42. {
  43.   ULONG l, r, m;
  44.  
  45.   l = 1; r = x;
  46.   while (l < r)
  47.     {
  48.       m = (l+r) / 2;
  49.       if (m > 46340) m = 46340;  /* avoid overflow when computing m*m */
  50.       if (m*m < x)
  51.         l = m+1;
  52.       else if (m*m > x)
  53.         r = m-1;
  54.       else
  55.         return (m);
  56.     }
  57.   return ((l+r)/2);
  58. }
  59.  
  60.  
  61. static void usage (void)
  62. {
  63.   fputs ("Usage: sieve [-p] <number>\n", stderr);
  64.   exit (1);
  65. }
  66.  
  67.  
  68. int main (int argc, char *argv[])
  69. {
  70.   ULONG sqrt_size, i, j, n, primes, size;
  71.   int incr, jincr, idx, print_flag;
  72.   size_t bytes;
  73.   char *p;
  74.   BYTE *bitmap;
  75.  
  76.   print_flag = FALSE;
  77.   for (idx = 1; idx < argc; ++idx)
  78.     if (strcmp (argv[idx], "-p") == 0)
  79.       print_flag = TRUE;
  80.     else
  81.       break;
  82.   if (argc - idx != 1)
  83.     usage ();
  84.   errno = 0;
  85.   size = strtoul (argv[idx], &p, 10);
  86.   if (errno != 0 || *p != 0 || size < 10 || size > 2000000000)
  87.     usage ();
  88.   bytes = BYTES (N (size) + 1);
  89.   bitmap = malloc (bytes);
  90.   if (bitmap == NULL)
  91.     {
  92.       fputs ("Out of memory\n", stderr);
  93.       exit (2);
  94.     }
  95.   memset (bitmap, 0, bytes);
  96.   sqrt_size = isqrt (size);
  97.   for (i = 5, incr = 4, n = 1; i <= sqrt_size; i += (incr=6-incr), ++n)
  98.     if (BIT_OFF (bitmap, n))
  99.       for (j = i, jincr = incr; j <= size/i; j += (jincr = 6-jincr))
  100.         SET_TRUE (bitmap, N(i*j));
  101.   if (print_flag)
  102.     printf ("2 3 ");
  103.   for (i = 5, incr = 4, n = 1, primes = 2; i <= size; i += (incr=6-incr), ++n)
  104.     if (BIT_OFF (bitmap, n))
  105.       {
  106.         ++primes;
  107.         if (print_flag)
  108.           printf ("%lu ", i);
  109.       }
  110.   printf ("\n%lu primes\n", primes);
  111.   return (0);
  112. }
  113.