/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