/home/toolbox/public_html/solutions/106/10680/c.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 180
28 #define MODV 10000
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<1000; i=i+2)
100 {
101 arr[i]=1;
102 }
103 for (i=11; i<1000; 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<1000; 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 /* now fill arr with lat digits, by proce each number from 1 to 1000000 */
119 /* curr will hold the prime factorization of the current factorial */
120 for (i=0; i<=numPrimes; i++)
121 {
122 curr[i] = 0;
123 }
124 arr[1]=1;
125 tmp = 1;
126 for (i=2; MAX_VALUE>i; i++)
127 {
128 /* for each poisble vlue */
129 printf(" process %d\n", i);
130 fctr(i);
131 DEBUG dump();
132 tmp = (tmp * factors[0]) % MODV; /* that other big prime factor */
133 for (p=1; p<=numPrimes; p++)
134 {
135 /* multiply all primes */
136 DEBUG printf("(tmp: %d) (factors[%d]: %d) (curr[%d]: %d\n", tmp, p, factors[p], p, curr[p]);
137 if (factors[p] > curr[p])
138 {
139 /* found a new prime factor of the LCM */
140 curr[p] = factors[p];
141 /* max change can never be more than 1 */
142 tmp = tmp * primes[p];
143 } /* found a new prime factor of the LCM */
144 } /* multiply all primes */
145 while (0 == (tmp % 10))
146 {
147 tmp = tmp / 10; /* clear off trailing 0s */
148 }
149 tmp = tmp % MODV;
150 arr[i] = tmp % 10;
151 dump();
152 DEBUG printf(" arr[%d] = %d\n", i, arr[i]);
153 } /* for each poisble vlue */
154 } /* FUNCTION init */
155
156 int getInput()
157 {
158 /* FUNCTION getInput */
159 int dataReadFlag;
160
161 scanf(" %d ", &num);
162 dataReadFlag = 0!= num;
163 return (dataReadFlag);
164 } /* FUNCTION getInput */
165
166 void process()
167 {
168 /* FUNCTION process */
169 printf("%d: ", num);
170 printf("%d\n", arr[num]);
171 } /* FUNCTION process */
172
173 int main()
174 {
175 /* main */
176 int moreToDo;
177
178 init();
179 moreToDo = getInput();
180 while (moreToDo)
181 {
182 /* while */
183 process();
184 moreToDo = getInput();
185 } /* while */
186
187 return EXIT_SUCCESS;
188 } /* main */
189