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