Computer Programming Contest Preparation

ToolBox - Source for: 106/10699/b.c



/home/toolbox/public_html/solutions/106/10699/b.c
    1 #include <stdio.h>
    2 #include <string.h>
    3 #include <sys/types.h>
    4 #include <sys/stat.h>
    5 #include <fcntl.h>
    6 #include <stdint.h>
    7 #include <math.h>
    8 #include <stdlib.h>
    9 
   10 #define TRUE  (1 == 1)
   11 #define FALSE (1 != 1)
   12 
   13 #define DEBUG if (FALSE)
   14 
   15 #define MAX_PRIMES 78505
   16 #define MAX_SIZE 1000005
   17 
   18 /*
   19  *  Author:
   20  *    Date: 2005-07-20
   21  * Purpose: practice
   22  * Problem: 10699
   23  */
   24 
   25 /*
   26  * This template reads data until a terminating value is reached.
   27  */
   28 
   29 int num;
   30 int primes[MAX_PRIMES];
   31 int buff[MAX_SIZE];
   32 int numPrimes;
   33 
   34 int init()
   35 {
   36     /* FUNCTION init */
   37     int i;
   38     int j;
   39     int k;
   40     int cnt;
   41     int t;
   42 
   43     numPrimes = 1;
   44     primes[1] = 2;
   45 
   46     /* sieve of erasthones */
   47     for (i=3; i<MAX_SIZE; i=i+2) buff[i]=i;
   48     for (i=3; i<MAX_SIZE; i=i+2)
   49         {
   50             /* loop through primes */
   51             if (0 != buff[i])
   52                 {
   53                     /* found a prime */
   54                     numPrimes++;
   55                     primes[numPrimes] = i;
   56                     for (j=i; j<MAX_SIZE; j=j+i+i)
   57                         {
   58                             /* mark out multiples */
   59                             buff[j] = 0;
   60                         } /* mark out multiples */
   61                 } /* found a prime */
   62         } /* loop through primes */
   63 
   64     /* empty the buffer */
   65     for (i=2; i<MAX_SIZE; i=i+1) buff[i]=0;
   66 
   67     /* fill in the primes */
   68     for (i=1; i<=numPrimes; i++)
   69         {
   70             /* do the easy parts */
   71             t = primes[i];
   72             buff[t] = 1;
   73             for (j=t*t; (j<MAX_SIZE) && (0 < j); j=j*t)
   74                 {
   75                     /* remove powers of the prime number */
   76                     buff[j] = 1;
   77                 } /* remove powers of the prime number */
   78         } /* do the easy parts */
   79     cnt = 0;
   80     for (j=2; j<MAX_SIZE; j++) if (0 == buff[j]) cnt++;
   81     printf("saved: %d\n", cnt);
   82 
   83     buff[1] = 0;
   84     for (i=2; i<MAX_SIZE; i++)
   85         {
   86             /* test all the numbers */
   87             if (0 == buff[i])
   88                 {
   89                     /* count factors */
   90                     t = i;
   91                     k = 1;
   92                     while (1 < t)
   93                         {
   94                             /* still another factor */
   95                             j = primes[k];
   96                             DEBUG printf("start %6d %6d %6d\n", i, t, j);
   97                             if (0 == (t % j))
   98                                 {
   99                                     buff[i]++;
  100                                 }
  101                             while (0 == (t % j))
  102                                 {
  103                                     t = t / j;
  104                                 }
  105                             if (0 != buff[t])
  106                                 {
  107                                     /* we have reduced the number to an already defined answer */
  108                                     DEBUG printf("Lookup success: %d %d\n", i, t);
  109                                     buff[i] = buff[i] + buff[t];
  110                                     t = 1;
  111                                 } /* we have reduced the number to an already defined answer */
  112                             DEBUG printf("t=%d    j=%d\n", t, j);
  113                             k++;
  114                         } /* still another factor */
  115                 } /* count factors */
  116         } /* test all the numbers */
  117     printf("buff[1]=0;");
  118     for (j=2; j<MAX_SIZE; j++)
  119         {
  120             if (0 == buff[j]) cnt++;
  121             printf("buf[%d]=%d;\n", j, buff[j]);
  122         }
  123     cnt=0;
  124     printf("left: %d\n", cnt);
  125 
  126 } /* FUNCTION init */
  127 
  128 int dump()
  129 {
  130     /* FUNCTION dump */
  131     int i;
  132     for (i=1; i<=numPrimes; i++)
  133         {
  134             /*dump each prime */
  135             printf("%4d:%5d\n", i, primes[i]);
  136         } /*dump each prime */
  137     printf("\nNumber of primes: %d\n\n", numPrimes);
  138 } /* FUNCTION dump */
  139 
  140 int getInput()
  141 {
  142     /* FUNCTION getInput */
  143     int dataReadFlag;
  144 
  145 
  146     dataReadFlag = (0 != 0);
  147     return (dataReadFlag);
  148 } /* FUNCTION getInput */
  149 
  150 void process()
  151 {
  152     /* FUNCTION process */
  153 } /* FUNCTION process */
  154 
  155 int main ()
  156 {
  157     /* main */
  158     int moreToDo;
  159 
  160     init();
  161 //   dump();
  162     moreToDo = getInput();
  163     while (moreToDo)
  164         {
  165             /* while */
  166             process();
  167             moreToDo = getInput();
  168         } /* while */
  169 
  170     return EXIT_SUCCESS;
  171 } /* main */
  172