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           8192            /* Up to what number? */
  22 #define SQRT_COUNT      91              /* 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 int main (void)
  39 {
  40     /* Clock variable */
  41     clock_t Ticks;
  42
  43     /* This is an example where register variables make sense */
  44     register unsigned char* S;
  45     register unsigned       I;
  46     register unsigned       J;
  47
  48     /* Output a header */
  49     printf ("Sieve benchmark - calculating primes\n");
  50     printf ("between 2 and %u\n", COUNT);
  51     printf ("Please wait patiently ...\n");
  52
  53     /* Read the clock */
  54     Ticks = clock();
  55
  56     /* Execute the sieve */
  57     I = 2;
  58     while (I < SQRT_COUNT) {
  59         if (Sieve[I] == 0) {
  60             /* Prime number - mark multiples */
  61             S = &Sieve[J = I*2];
  62             while (J < COUNT) {
  63                 *S = 1;
  64                 S += I;
  65                 J += I;
  66             }
  67         }
  68         ++I;
  69     }
  70
  71     /* Calculate the time used */
  72     Ticks = clock() - Ticks;
  73
  74     /* Print the time used */
  75     printf ("Time used: %lu ticks\n", Ticks);
  76     printf ("Press Q to quit, any other key for list\n");
  77
  78     /* Wait for a key and print the list if not 'Q' */
  79     if (toupper (cgetc()) != 'Q') {
  80         /* Print the result */
  81         for (I = 2; I < COUNT; ++I) {
  82             if (Sieve[I] == 0) {
  83                 printf ("%4d\n", I);
  84             }
  85             if (kbhit() && toupper (cgetc()) == 'Q') {
  86                 break;
  87             }
  88         }
  89     }
  90
  91     return EXIT_SUCCESS;
  92 }
  93
  94
  95