/home/toolbox/public_html/solutions/106/10680/d.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 MAX_PRIMES 79000
28 #define MODV MAX_VALUE
29
30 int num; /* deired number to return lat non-zero digit of */
31 int arr[MAX_VALUE+3]; /* buffer for sieve, cache of last digit */
32 int primes[MAX_PRIMES];
33 int numPrimes;
34 int factors[MAX_PRIMES]; /* prime factorization of the number we area bout to process */
35 int curr[MAX_PRIMES]; /* running prime factorization of factorial */
36
37 void fctr(int num)
38 {
39 /* FUNCTION fctr */
40 int p;
41 int leftover;
42
43 /* if the number has a prime factor > sqrt(MAX_VALUE),
44 * then leftover will hve that large prime factor
45 * else leftover will be 1
46 * leftover will be stored in 0th location of factors
47 */
48
49 leftover = num;
50 for (p=1; numPrimes>=p; p++)
51 {
52 factors[p] = 0;
53 }
54 p = 1;
55 while ((1 < leftover) && (p<=numPrimes))
56 {
57 /* factor num */
58 while (0 == (leftover % primes[p]))
59 {
60 /* this is a factor */
61 factors[p] = factors[p] + 1;
62 leftover = leftover / primes[p];
63 } /* this is a factor */
64 p++;
65 } /* factor num */
66 factors[0] = leftover;
67 } /* FUNCTION fctr */
68
69 void dump()
70 {
71 /* FUNCTION dump */
72 int p;
73
74 for (p=0; p<=numPrimes; p++)
75 {
76 if ((0 != curr[p]) || (0!= factors[p]))
77 {
78 printf("%d - %d: curr: %d factors: %d\n ", p, primes[p], curr[p], factors[p]);
79 }
80 }
81 printf("\n");
82 } /* FUNCTION dump */
83
84 int init()
85 {
86 /* FUNCTION init */
87 int i;
88 int j;
89 int p;
90 int tmp;
91
92 /* make prime list */
93 numPrimes = 4;
94 primes[1] = 2;
95 primes[2] = 3;
96 primes[3] = 5;
97 primes[4] = 7;
98 /* sieve of erasthones */
99 for (i=11; i<MODV; i=i+2)
100 {
101 arr[i]=1;
102 }
103 for (i=11; i<MODV; i=i+2)
104 {
105 /* loop through primes */
106 if (0 != arr[i])
107 {
108 /* found a prime */
109 numPrimes++;
110 primes[numPrimes] = i;
111 for (j=i+i+i; j<MODV; j=j+i+i)
112 {
113 /* mark out multiples */
114 arr[j] = 0;
115 } /* mark out multiples */
116 } /* found a prime */
117 } /* loop through primes */
118 DEBUG printf(" numPrimes %d\n", numPrimes);
119 /* now fill arr with lat digits, by proce each number from 1 to 1000000 */
120 /* curr will hold the prime factorization of the current factorial */
121 for (i=0; i<=numPrimes; i++)
122 {
123 curr[i] = 0;
124 }
125 arr[1]=1;
126 tmp = 1;
127 for (i=2; MAX_VALUE>i; i++)
128 {
129 /* for each poisble vlue */
130 DEBUG printf(" process %d\n", i);
131 fctr(i);
132 DEBUG dump();
133 tmp = (tmp * factors[0]) % MODV; /* that other big prime factor */
134 for (p=1; p<=numPrimes; p++)
135 {
136 /* multiply all primes */
137 DEBUG printf("(tmp: %d) (factors[%d]: %d) (curr[%d]: %d\n", tmp, p, factors[p], p, curr[p]);
138 if (factors[p] > curr[p])
139 {
140 /* found a new prime factor of the LCM */
141 curr[p] = factors[p];
142 /* max change can never be more than 1 */
143 tmp = tmp * primes[p];
144 } /* found a new prime factor of the LCM */
145 } /* multiply all primes */
146 while (0 == (tmp % 10))
147 {
148 tmp = tmp / 10; /* clear off trailing 0s */
149 }
150 tmp = tmp % MODV;
151 arr[i] = tmp % 10;
152 DEBUG dump();
153 DEBUG printf(" arr[%d] = %d\n", i, arr[i]);
154 } /* for each poisble vlue */
155 } /* FUNCTION init */
156
157 int getInput()
158 {
159 /* FUNCTION getInput */
160 int dataReadFlag;
161
162 scanf(" %d ", &num);
163 dataReadFlag = 0!= num;
164 return (dataReadFlag);
165 } /* FUNCTION getInput */
166
167 void process()
168 {
169 /* FUNCTION process */
170 printf("%d: ", num);
171 printf("%d\n", arr[num]);
172 } /* FUNCTION process */
173
174 int main()
175 {
176 /* main */
177 int moreToDo;
178
179 init();
180 moreToDo = getInput();
181 while (moreToDo)
182 {
183 /* while */
184 process();
185 moreToDo = getInput();
186 } /* while */
187
188 return EXIT_SUCCESS;
189 } /* main */
190