Computer Programming Contest Preparation

ToolBox - Source for: 106/10680/a.c



/home/toolbox/public_html/solutions/106/10680/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  *  Author: Isaac Traxler
   17  *    Date: 2020-03-05
   18  * Purpose: fun
   19  * Problem: 10680 - LCM
   20  */
   21 
   22 /*
   23  * This template reads data until a terminating value is reached.
   24  */
   25 
   26 #define MAX_VALUE 1000005
   27 #define SQRT_MAX_VALUE 1001
   28 #define MAX_PRIMES 79000
   29 #define MODV 1000
   30 
   31 int num; /* desired number to return lat non-zero digit of */
   32 int sieve[MAX_VALUE+3]; /* bitmap of prime numbers */
   33 int arr[MAX_VALUE+3];  /* lookup array for last digit */
   34 int primes[MAX_PRIMES];
   35 int numPrimes;
   36 
   37 void doSieve()
   38 {
   39     /* FUNCTION doSieve */
   40     int i;
   41     int j;
   42 
   43     /* make prime list */
   44     numPrimes = 1;
   45     primes[1] = 2;
   46     /* sieve of erasthones */
   47     /* primes will be an array of numPrimes prime numbers
   48      * sieve will be a flag array: 0 says not prime, 1 says prime */
   49     sieve[1] = 1;
   50     sieve[2] = 2;
   51     for (i=4; i<MAX_VALUE; i=i+2)
   52         {
   53             sieve[i]=1;    /* mark off multiples of 2 right off bat */
   54         }
   55     for (i=3; i<MAX_VALUE; i=i+2)
   56         {
   57             sieve[i]=i;    /* set odd numbers to acctiual value */
   58         }
   59     for (i=3; i<MAX_VALUE; i=i+2)  /* process odds since evens already set to 1 */
   60         {
   61             /* loop through primes */
   62             if (1 < sieve[i])
   63                 {
   64                     /* found a prime */
   65                     numPrimes++;
   66                     primes[numPrimes] = i;
   67                     for (j=i+i; j<MAX_VALUE; j=j+i)
   68                         {
   69                             /* mark out multiples */
   70                             sieve[j] = 1;
   71                         } /* mark out multiples */
   72                 } /* found a prime */
   73         } /* loop through primes */
   74 } /* FUNCTION doSieve */
   75 
   76 void doPrimePowers()
   77 {
   78     /* FUNCTION doPrimePowers */
   79     /*
   80      * all of the powers of a prime will alse impact final digit
   81      * This function will add those factors back in
   82      */
   83     int i;
   84     int tmp;
   85 
   86     for (i=1; i<SQRT_MAX_VALUE; i++)
   87         {
   88             /* for each prime */
   89             tmp = primes[i] * primes[i];
   90             while (tmp < MAX_VALUE)
   91                 {
   92                     /* add in powers of each prime */
   93                     sieve[tmp] = primes[i];
   94                     tmp = tmp * primes[i];
   95                 } /* add in powers of each prime */
   96         } /* for each prime */
   97 } /* FUNCTION doPrimePowers */
   98 
   99 void calcLastDigit()
  100 {
  101     /* FUNCTION calcLastDigit */
  102     int i;
  103     int tmp = 1;
  104 
  105     arr[1] = 1;
  106     for (i=2; i<MAX_VALUE; i++)
  107         {
  108             /* calculate last digit of evey possible value */
  109             tmp = tmp * sieve[i];
  110             if (0  == (tmp % 10))
  111                 {
  112                     tmp = tmp / 10;
  113                 }
  114             tmp = tmp % MODV;
  115             arr[i] = tmp % 10;
  116         } /* calculate last digit of evey possible value */
  117 }/* FUNCTION calcLastDigit */
  118 
  119 void init()
  120 {
  121     /* FUNCTION init */
  122     doSieve();
  123     doPrimePowers();
  124     calcLastDigit();
  125 } /* FUNCTION init */
  126 
  127 int getInput()
  128 {
  129     /* FUNCTION getInput */
  130     int dataReadFlag;
  131 
  132     scanf(" %d ", &num);
  133     dataReadFlag = 0!= num;
  134     return (dataReadFlag);
  135 } /* FUNCTION getInput */
  136 
  137 void process()
  138 {
  139     /* FUNCTION process */
  140     printf("%d\n", arr[num]);
  141 } /* FUNCTION process */
  142 
  143 int main()
  144 {
  145     /* main */
  146     int moreToDo;
  147 
  148     init();
  149     moreToDo = getInput();
  150     while (moreToDo)
  151         {
  152             /* while */
  153             process();
  154             moreToDo = getInput();
  155         } /* while */
  156 
  157     return EXIT_SUCCESS;
  158 } /* main */
  159