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     /* Read the clock */
  49     Ticks = clock();
  50
  51     /* Execute the sieve */
  52     I = 2;
  53     while (I < SQRT_COUNT) {
  54         if (Sieve[I] == 0) {
  55             /* Prime number - mark multiples */
  56             S = &Sieve[J = I*2];
  57             while (J < COUNT) {
  58                 *S = 1;
  59                 S += I;
  60                 J += I;
  61             }
  62         }
  63         ++I;
  64     }
  65
  66     /* Calculate the time used */
  67     Ticks = clock() - Ticks;
  68
  69     /* Print the time used */
  70     printf ("Time used: %lu ticks\n", Ticks);
  71     printf ("Press Q to quit, any other key for list\n");
  72
  73     /* Wait for a key and print the list if not 'Q' */
  74     if (toupper (cgetc()) != 'Q') {
  75         /* Print the result */
  76         for (I = 2; I < COUNT; ++I) {
  77             if (Sieve[I] == 0) {
  78                 printf ("%4d\n", I);
  79             }
  80             if (kbhit() && toupper (cgetc()) == 'Q') {
  81                 break;
  82             }
  83         }
  84     }
  85
  86     return EXIT_SUCCESS;
  87 }
  88
  89
  90