Computer Programming Contest Preparation

ToolBox - Source for: 2/294/a.c



/home/toolbox/public_html/solutions/2/294/a.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 
   16 
   17 /*
   18  *  Author: Isaac Traxler
   19  *    Date: 2015-09-22
   20  * Purpose: fun
   21  * Problem: 294
   22  */
   23 
   24 /*
   25  * This template reads data a counted number of times
   26  */
   27 
   28 
   29 #define MAX_PRIMES 6500
   30 #define MAX_SIZE 32000
   31 #define MAX_BUFFER 1000000001
   32 
   33 /* buffer is used for:
   34    1) buffer of raw numbers for sieve
   35    2) cache any computed factor
   36 */
   37 unsigned short buff[MAX_BUFFER] = { 0 };
   38 int primes[MAX_PRIMES];
   39 int primeCnt;
   40 int numberOfTimes;
   41 int L;
   42 int U;
   43 
   44 
   45 void init()
   46 {
   47     /* FUNCTION init */
   48     int i;
   49     int j;
   50 
   51     primes[0] = 2;
   52     primeCnt = 1;
   53 
   54     /* sieve of erasthones */
   55     for (i=0,j=3; i<MAX_SIZE; i++,j=j+2)
   56         {
   57             buff[i]=j;
   58         }
   59     for (i=0; (MAX_PRIMES>primeCnt)&&(MAX_SIZE>i); i++)
   60         {
   61             /* loop through primes */
   62             if (0 != buff[i])
   63                 {
   64                     /* found a prime */
   65                     DEBUG printf("%d -- buff[%d] = %d\n", primeCnt, i, buff[i]);
   66                     primes[primeCnt++] = buff[i];
   67                     for (j=i+buff[i]; j<MAX_SIZE; j=j+buff[i])
   68                         {
   69                             /* mark out multiples */
   70                             buff[j] = 0;
   71                         } /* mark out multiples */
   72                     buff[i] = 0;
   73                 } /* found a prime */
   74         } /* loop through primes */
   75     DEBUG printf("pime cnt %d\n", primeCnt);
   76     scanf(" %d ", &numberOfTimes);
   77 } /* FUNCTION init */
   78 
   79 void dump()
   80 {
   81     /* FUNCTION dump */
   82 } /* FUNCTION dump */
   83 
   84 void getInput()
   85 {
   86     /* FUNCTION getInput */
   87     scanf(" %d %d ", &L, &U);
   88 } /* FUNCTION getInput */
   89 
   90 int factor(int num)
   91 {
   92     /* FUNCTION factor */
   93     int tmp;
   94     int i = 0;
   95     int tot = 1;
   96     int ptot;
   97 
   98     if (1 == num)
   99         {
  100             tot = 1;
  101         }
  102     else
  103         {
  104             /* work to do */
  105             tmp = num;
  106             while (1 < tmp)
  107                 {
  108                     /* while */
  109                     ptot = 1;
  110                     while (0 == (tmp % primes[i]))
  111                         {
  112                             /* divisor found */
  113                             tmp = tmp / primes[i];
  114                             ptot++;
  115                         } /* divisor found */
  116                     if (1 < ptot)
  117                         {
  118                             tot = tot * ptot;
  119                         }
  120                     i++;
  121                     if ((1 < tmp) && ((primes[i] * primes[i]) > num))
  122                         {
  123                             tmp = 1;    /* only check numbers less than square root */
  124                             tot = tot * 2;
  125                         }
  126                 } /* while */
  127         } /* work to do */
  128     return tot;
  129 } /* FUNCTION factor */
  130 
  131 void process()
  132 {
  133     /* FUNCTION process */
  134     int i;
  135     int mx = 0;
  136     int save;
  137 
  138     DEBUG printf("Between %d and %d\n", L, U);
  139     for (i=L; i<=U; i++)
  140         {
  141             /* proces each possible number */
  142             if (0 == buff[i])
  143                 {
  144                     /* not cached */
  145                     DEBUG printf("factoring: %d ", i);
  146                     buff[i] = factor(i);
  147                     DEBUG printf("   factors = %d\n", buff[i]);
  148                 } /* not cached */
  149             if (buff[i] > mx)
  150                 {
  151                     mx = buff[i];
  152                     save = i;
  153                 }
  154         } /* proces each possible number */
  155     printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, U, save, mx);
  156 } /* FUNCTION process */
  157 
  158 int main()
  159 {
  160     /* main */
  161     int i;
  162 
  163     init();
  164     for(i=0; i<numberOfTimes; i++)
  165         {
  166             /* for */
  167             getInput();
  168             process();
  169         } /* for */
  170 
  171     return EXIT_SUCCESS;
  172 } /* main */
  173