git.sur5r.net Git - cc65/blob - samples/sieve.c

   1 /*
   2 ** Calculate all primes up to a specific number.
   3 */
   4
   5
   6
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9 #include <ctype.h>
  10 #include <time.h>
  11 #include <conio.h>
  12
  13
  14 /* Workaround missing clock stuff */
  15 #ifdef __APPLE2__
  16 #  define clock()               0
  17 #  define CLOCKS_PER_SEC        1
  18 #endif
  19
  20
  21
  22 /*****************************************************************************/
  23 /*                                   Data                                    */
  24 /*****************************************************************************/
  25
  26
  27
  28 #define COUNT           16384           /* Up to what number? */
  29 #define SQRT_COUNT      128             /* Sqrt of COUNT */
  30
  31 static unsigned char Sieve[COUNT];
  32
  33
  34
  35 /*****************************************************************************/
  36 /*                                   Code                                    */
  37 /*****************************************************************************/
  38
  39
  40
  41 #pragma static-locals(1);
  42
  43
  44
  45 static char ReadUpperKey (void)
  46 /* Read a key from console, convert to upper case and return */
  47 {
  48     return toupper (cgetc ());
  49 }
  50
  51
  52
  53 int main (void)
  54 {
  55     /* Clock variable */
  56     clock_t Ticks;
  57     unsigned Sec;
  58     unsigned Milli;
  59
  60     /* This is an example where register variables make sense */
  61     register unsigned char* S;
  62     register unsigned       I;
  63     register unsigned       J;
  64
  65     /* Output a header */
  66     printf ("Sieve benchmark - calculating primes\n");
  67     printf ("between 2 and %u\n", COUNT);
  68     printf ("Please wait patiently ...\n");
  69
  70     /* Read the clock */
  71     Ticks = clock();
  72
  73     /* Execute the sieve */
  74     I = 2;
  75     while (I < SQRT_COUNT) {
  76         if (Sieve[I] == 0) {
  77             /* Prime number - mark multiples */
  78             J = I*2;
  79             S = &Sieve[J];
  80             while (J < COUNT) {
  81                 *S = 1;
  82                 S += I;
  83                 J += I;
  84             }
  85         }
  86         ++I;
  87     }
  88
  89     /* Calculate the time used */
  90     Ticks = clock() - Ticks;
  91     Sec = (unsigned) (Ticks / CLOCKS_PER_SEC);
  92     Milli = ((Ticks % CLOCKS_PER_SEC) * 1000) / CLOCKS_PER_SEC;
  93
  94     /* Print the time used */
  95     printf ("Time used: %u.%03u seconds\n", Sec, Milli);
  96     printf ("Q to quit, any other key for list\n");
  97
  98     /* Wait for a key and print the list if not 'Q' */
  99     if (ReadUpperKey () != 'Q') {
 100         /* Print the result */
 101         J = 0;
 102         for (I = 2; I < COUNT; ++I) {
 103             if (Sieve[I] == 0) {
 104                 printf ("%4d\n", I);
 105                 if (++J == 23) {
 106                     printf ("Q to quit, any other key continues\n");
 107                     if (ReadUpperKey () == 'Q') {
 108                         break;
 109                     }
 110                     J = 0;
 111                 }
 112             }
 113             if (kbhit() && ReadUpperKey () == 'Q') {
 114                 break;
 115             }
 116         }
 117     }
 118
 119     return EXIT_SUCCESS;
 120 }
 121
 122
 123