home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 5.ddi / MWHC.005 / W < prev    next >
Encoding:
Text File  |  1992-03-30  |  1.4 KB  |  49 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. #include <stdio.h>
  13.  
  14. typedef enum{False,True} Boolean;
  15.  
  16. void main () {
  17. #  define SIZE 8190
  18.    static Boolean Primes[SIZE+1];
  19.    int I,Prime,K,Count,iter;
  20.    /* The program currently computes the primes only once.        */
  21.    /* For a more time-consuming test, change ITERATIONS to a higher    */
  22.    /* value.                                */
  23. #  define ITERATIONS 1
  24.  
  25.    printf("Begin computation of primes...\n");
  26.    for (iter = 1; iter <= ITERATIONS; iter++) {
  27.       Count = 0;
  28.       for (I = 0; I <= SIZE; I++)
  29.      Primes[I] = True;
  30.       for (I = 0; I <= SIZE; I++)
  31.      if (Primes[I]) {
  32.         Prime = 2*I+3;
  33.         K = I+Prime;
  34.         while (K <= SIZE) {
  35.            Primes[K] = False;
  36.            K += Prime;
  37.            }
  38.         Count++;
  39.         }
  40.  
  41.       }
  42.  
  43.    printf("%d primes between 3 and 16383:\n",Count);
  44.    for (I = 0; I <= SIZE; I++)
  45.       if (Primes[I])
  46.      printf("%8d",2*I+3);
  47.    printf("\nEnd of sieve program.\n");
  48.    }
  49.