home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c220 / 4.ddi / DEMOS / MSIEVE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-16  |  4.5 KB  |  133 lines
  1. #include <stdio.h>
  2.  
  3. typedef enum{False,True} Boolean;
  4.  
  5. extern void * malloc(unsigned int);
  6. extern void free(void *);
  7. extern long clock();
  8.  
  9. #define Trace_malloc 0
  10.  
  11. unsigned Size_mem() {
  12.    unsigned int Alloc_amount = 0x1ff_ffff, /* 32 mb. */
  13.            Sum = 0;
  14.    void try() {
  15.       void *p;
  16.       do {
  17.          p = malloc(Alloc_amount);
  18.          Alloc_amount = Alloc_amount / 2;
  19.       } while (p == 0 && Alloc_amount > 256);  
  20.       if (Trace_malloc) printf("Malloc-ed %d: %x\n",Alloc_amount*2,p);   
  21.       if (p != 0) {
  22.            Sum += Alloc_amount*2;
  23.          if (Alloc_amount > 256) try();
  24.          }
  25.       if (p != 0) free(p);
  26.       }
  27.    try();
  28.    return Sum;
  29.    }    
  30.  
  31. char YesNo(char *msg) {
  32.    char response;
  33.    printf("%s (y/n)?",msg);
  34.    scanf(" %c",&response);
  35.    return response == 'y' || response == 'Y';
  36.    } 
  37.  
  38. void print_banner() {
  39.    static char * banner[] = {
  40.     "IMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM;", 
  41.     ":                   *MIGHTY* SIEVE!!!                      :",
  42.     "HMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM<",
  43.     "IMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM;", 
  44.     ":  This program computes the primes up to the number you   :",
  45.     ":  specify by using the sieve of Eratosthenes.  An array   :",
  46.     ":  of booleans is dynamically allocated from  the  mega-   :",
  47.     ":  bytes  available  under  the 32-bit adddress space of   :",
  48.     ":  80386 protected mode.  The primes  are  computed  and   :",
  49.     ":  then printed if you wish.                               :",
  50.     ":  (Make sure you check each one; the computer might make  :",
  51.     ":  a misteak!)                                             :",
  52.     ":DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD:",
  53.     ":    Brought to you by the friendly folks at MetaWare      :",
  54.     ":   and the providers of this protected-mode environment.  :",
  55.     "HMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM<"};
  56.  
  57.    int I;
  58.    for (I = 0; I < sizeof(banner)/sizeof(char *); I++)
  59.       printf("\t%s\n",banner[I]);
  60.    }
  61.  
  62. void main (int argc, char** argv) {
  63.    int Size;
  64.    Boolean *Primes;
  65.    void init() {
  66. #     define DEFAULT 16383
  67.       /* Get the parameters. */
  68.       /* If one or more arguments, assume Size = 8190 (the standard sieve). */
  69.       if (argc > 1) Size = DEFAULT;
  70.       else {
  71.       L: printf("Enter the highest number that you wish tested for primality.\n"
  72.               "Enter 0 for the default of %d.\n"
  73.                 "Now enter your number:",DEFAULT,argv);
  74.            scanf("%d",&Size);
  75.            if (Size == 0) Size = DEFAULT;
  76.            if (Size <= 1*2+3) {
  77.               printf("Sorry, please try something a little bigger.\n");
  78.               goto L;
  79.               }
  80.          }
  81.       Size = (Size-3)/2;
  82.    L2:printf("\nAllocating an array of %d elements...\n", Size+1); 
  83.       Primes = (Boolean *) malloc(Size+1);
  84.       if (Trace_malloc) printf("Malloc-ed %d: %x\n",Size+1,Primes);
  85.       if (Primes == 0) {
  86.            printf("Sorry, I don't seem to have that much memory...hang on...\n");
  87.            printf("I seem to be able to allocate up to %d bytes for my array.\n",
  88.                Size = Size_mem());
  89.            Size--;        /* In case we allocate; match what we print. */
  90.            if (YesNo("Do you want me to use that much")) goto L2;
  91.            else goto L;
  92.            }
  93.       }
  94.    int Count,iter;
  95.    /* The program currently computes the primes only once.        */
  96.    /* For a more time-consuming test, change ITERATIONS to a higher    */
  97.    /* value.                                */
  98. #  define ITERATIONS 1
  99.    print_banner();   
  100.    init();
  101.  
  102.    printf("\nBegin computation of primes...\n");
  103.    long start_time = clock();
  104.    for (iter = 1; iter <= ITERATIONS; iter++) {
  105.       int I,Prime,K;
  106.       Count = 0;
  107.       _fill_char(&Primes[0],Size,1);
  108.       /* for (I = 0; I <= Size; I++) Primes[I] = True; */
  109.       for (I = 0; I <= Size; I++)  
  110.          if (Primes[I]) {
  111.         Prime = 2*I+3;
  112.         K = I+Prime;
  113.         while (K <= Size) {
  114.            Primes[K] = False;
  115.            K += Prime;
  116.            }
  117.         Count++;
  118.             }
  119.       }
  120.  
  121.    if (start_time != 0) 
  122.       printf("You made me work for %d hundredths of a second.\n\n",
  123.            clock()-start_time);
  124.    printf("There are %d primes between 3 and %d:\n",Count,2*Size+3);
  125.    if (ITERATIONS != 1) printf("(I computed them %d times.)\n",ITERATIONS);        
  126.    if (YesNo("Do you want to see them")) {
  127.       register int I;    
  128.       for (I = 0; I <= Size; I++)
  129.          if (Primes[I]) printf("%7d ",2*I+3);
  130.       }   
  131.    printf("\nEnd of sieve program.\n");
  132.    }
  133.