home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 5.ddi / MWHC.005 / C < prev    next >
Encoding:
Text File  |  1992-04-14  |  1.7 KB  |  70 lines
  1. /* The odd numbers between 3 and 16383, inclusive, are represented by
  2.   the numbers between 0 and 8191, inclusive, according to the following scheme:
  3.   if n in [0..8191], 2n+3 is the represented number.
  4.   Each number 2n+3 is considered in turn.
  5.   Its first odd multiple is (2n+3)*3, or 6n+9, or 2*(n+2n+3)+3.
  6.   Thus the statements
  7.     Prime = 2*I+3;           -- 2n+3
  8.   which computes the prime, and
  9.     K = I+Prime;           -- 2K+3 = 2*(n+2n+3)+3 = 6n+9
  10.   which computes the index of the first odd multiple.
  11. */
  12.  
  13.  
  14. #include <time.h>
  15.  
  16. double second()
  17. {
  18. return (double)(((double)(clock()))/((double)(CLOCKS_PER_SEC))) ;
  19. }
  20.  
  21. /* set the # of iterations as desired */
  22. #ifndef ITERATIONS
  23. #  define ITERATIONS 1
  24. #endif
  25.  
  26. typedef enum{False,True} Boolean;
  27.  
  28.  
  29. void main () {
  30. #  define SIZE 8190
  31.    static Boolean Primes[SIZE+1];
  32.    int I,Prime,K,Count,iter;
  33.    double t1, t2, t;
  34.  
  35.    printf("Begin computation of primes...\n");
  36.    t1=second();
  37.    for (iter = 1; iter <= ITERATIONS; iter++) {
  38.       Count = 0;
  39.       for (I = 0; I <= SIZE; I++)
  40.      Primes[I] = True;
  41.       for (I = 0; I <= SIZE; I++)
  42.      if (Primes[I]) {
  43.         Prime = 2*I+3;
  44.         K = I+Prime;
  45.         while (K <= SIZE) {
  46.            Primes[K] = False;
  47.            K += Prime;
  48.            }
  49.         Count++;
  50.         }
  51.  
  52.       }
  53.    t2=second();
  54.  
  55.    t = t2 - t1;
  56.  
  57. #ifdef BENCHMARK
  58.    printf("Computing and counting primes between 3 and 16383:\n");
  59.    printf("  Number of primes: %d\n", Count);
  60.    printf("  Number of Iterations: %d\n", ITERATIONS);
  61.    printf("  Time taken: %lf seconds\n", t);
  62. #else
  63.    printf("%d primes between 3 and 16383:\n",Count);
  64.    for (I = 0; I <= SIZE; I++)
  65.       if (Primes[I])
  66.      printf("%8d",2*I+3);
  67.    printf("\nEnd of sieve program.\n");
  68. #endif
  69.    }
  70.