/home/toolbox/public_html/solutions/106/10680/f.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 10000000
29
30 int num; /* deired number to return lat non-zero digit of */
31 int sieve[MAX_VALUE+3]; /* bitmap of prime numbers */
32 int arr[MAX_VALUE+3]; /* lookup array for last digit */
33 int curr[MAX_PRIMES]; /* prime factor of LCM */
34 int primes[MAX_PRIMES];
35 int numPrimes;
36
37 void dump()
38 {
39 /* FUNCTION dump */
40 } /* FUNCTION dump */
41
42 void doSieve()
43 {
44 /* FUNCTION doSieve */
45 int i;
46 int j;
47
48 /* make prime list */
49 numPrimes = 0;
50 /* sieve of erasthones */
51 /* primes will be an array of numPrimes prime numbers
52 * sieve will be a flag array: 0 says not prime, 1 says prime */
53 for (i=2; i<MAX_VALUE; i++)
54 {
55 arr[i]=1;
56 }
57 for (i=2; i<MAX_VALUE; i++)
58 {
59 /* loop through primes */
60 if (0 != arr[i])
61 {
62 /* found a prime */
63 numPrimes++;
64 primes[numPrimes] = i;
65 for (j=i+i; j<MAX_VALUE; j=j+i)
66 {
67 /* mark out multiples */
68 arr[j] = 0;
69 } /* mark out multiples */
70 } /* found a prime */
71 } /* loop through primes */
72 } /* FUNCTION doSieve */
73
74 int init()
75 {
76 /* FUNCTION init */
77 int i;
78 int j;
79 int p;
80 int tmp;
81 long long part;
82 int cnt;
83
84 doSieve();
85 DEBUG printf(" numPrimes %d\n", numPrimes);
86 /* now fill arr with last digits, by process each number from 1 to 1000000 */
87 /* curr will hold the prime factorization of the current factorial */
88 for (i=0; i<=numPrimes; i++)
89 {
90 curr[i] = 0;
91 }
92 arr[1]=1;
93 part = 1;
94 for (i=2; MAX_VALUE>i; i++)
95 {
96 /* for each possible value */
97 DEBUG printf("processing %d\n", i);
98 tmp = i;
99 p = 1;
100 while (1 < tmp)
101 {
102 /* factor tmp */
103 if (1 == sieve[tmp])
104 {
105 /* found a prime */
106 if (0 == curr[tmp])
107 {
108 /* found a first for a prime */
109 curr[tmp]++;
110 part = (part * (tmp % 100)) % MODV;
111 } /* found a first for a prime */
112 tmp = 1;
113 } /* found a prime */
114 else
115 {
116 /* tmp is not prime yet */
117 DEBUG printf("(i %d) (p[%d] %d) (tmp %d)\n", i, p, primes[p], tmp);
118 /* cnt how many times prime[p] divides into tmp */
119 if (p > numPrimes)
120 {
121 printf("missing a prime :%d)\n", tmp);
122 }
123 cnt = 0;
124 while (0 == (tmp % primes[p]))
125 {
126 cnt++;
127 tmp = tmp / primes[p];
128 }
129 /* it is possible tmp has one more prime[p] factor that curr */
130 if (cnt > curr[primes[p]])
131 {
132 /* found a new factor */
133 part = (part * primes[p]) % MODV;
134 curr[primes[p]]++;
135 } /* found a new factor */
136 p++;
137 } /* tmp is not prime yet */
138 } /* factor tmp */
139 while (0 == (part % 10))
140 {
141 part = part / 10; /* clear off trailing 0s */
142 }
143 arr[i] = part % 10;
144 printf("(arr[%d] %d) (part %ld)\n", i, arr[i], part);
145 } /* for each possible value */
146 } /* FUNCTION init */
147
148 int getInput()
149 {
150 /* FUNCTION getInput */
151 int dataReadFlag;
152
153 scanf(" %d ", &num);
154 dataReadFlag = 0!= num;
155 return (dataReadFlag);
156 } /* FUNCTION getInput */
157
158 void process()
159 {
160 /* FUNCTION process */
161 printf("%d: ", num);
162 printf("%d\n", arr[num]);
163 } /* FUNCTION process */
164
165 int main()
166 {
167 /* main */
168 int moreToDo;
169
170 init();
171 moreToDo = getInput();
172 while (moreToDo)
173 {
174 /* while */
175 process();
176 moreToDo = getInput();
177 } /* while */
178
179 return EXIT_SUCCESS;
180 } /* main */
181