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 int main (void)
  35 {
  36     /* Clock variable */
  37     clock_t Ticks;
  38
  39     /* This is an example where register variables make sense */
  40     register unsigned char* S;
  41     register unsigned       I;
  42     register unsigned       J;
  43
  44     /* Read the clock */
  45     Ticks = clock();
  46
  47     /* Execute the sieve */
  48     I = 2;
  49     while (I < SQRT_COUNT) {
  50         if (Sieve[I] == 0) {
  51             /* Prime number - mark multiples */
  52             S = &Sieve[J = I*2];
  53             while (J < COUNT) {
  54                 *S = 1;
  55                 S += I;
  56                 J += I;
  57             }
  58         }
  59         ++I;
  60     }
  61
  62     /* Calculate the time used */
  63     Ticks = clock() - Ticks;
  64
  65     /* Print the time used and wait for a key */
  66     printf ("Time used: %lu ticks\n", Ticks);
  67     printf ("Press Q to quit, any other key for list\n");
  68     if (toupper (cgetc()) == 'Q') {
  69         exit (EXIT_SUCCESS);
  70     }
  71
  72     /* Print the result */
  73     for (I = 2; I < COUNT; ++I) {
  74         if (Sieve[I] == 0) {
  75             printf ("%4d\n", I);
  76         }
  77         if (kbhit() && toupper (cgetc()) == 'q') {
  78             break;
  79         }
  80     }
  81
  82     return EXIT_SUCCESS;
  83 }
  84
  85
  86