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