/home/toolbox/public_html/solutions/100/10006/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: 2015-03-30
18 * Purpose:
19 * Problem: 10006
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24
25 561
26 1105
27 1729
28 2465
29 2821
30 6601
31 8911
32 10585
33 15841
34 29341
35 41041
36 46657
37 52633
38 62745
39 63973
40
41 */
42
43 #define MAX_PRIMES 6500
44 #define MAX_SIZE 65000
45 #define MAX_CAR 20
46
47 int n;
48
49 int buff[MAX_SIZE];
50 int primes[MAX_PRIMES];
51 int primeCnt;
52 int car[MAX_CAR];
53 int carCnt;
54
55 void init()
56 {
57 /* FUNCTION init */
58 int i;
59 int j;
60
61 buff[0] = 0;
62 buff[1] = 0;
63 buff[2] = 2;
64 primeCnt = 0;
65
66 /* sieve of erasthones */
67 for (i=3; i<MAX_SIZE; i=i+2)
68 {
69 buff[i]=i;
70 buff[i+1]=0;
71 }
72 for (i=3; i<MAX_SIZE; i=i+2)
73 {
74 /* loop through primes */
75 if (0 != buff[i])
76 {
77 /* found a prime */
78 primes[primeCnt++] = i;
79 DEBUG printf("%d\n", i);
80 for (j=i+i+i; j<MAX_SIZE; j=j+i+i)
81 {
82 /* mark out multiples */
83 buff[j] = 0;
84 } /* mark out multiples */
85 } /* found a prime */
86 } /* loop through primes */
87 DEBUG printf("pime cnt %d\n", primeCnt);
88 } /* FUNCTION init */
89
90 void dump()
91 {
92 /* FUNCTION dump */
93 } /* FUNCTION dump */
94
95 int getInput()
96 {
97 /* FUNCTION getInput */
98 int dataReadFlag;
99
100 scanf(" %d ", &n);
101 dataReadFlag = (0 != n);
102 return (dataReadFlag);
103 } /* FUNCTION getInput */
104
105 int prime(int x)
106 {
107 /* FUNCTION prime */
108 return (0 != buff[x]);
109 } /* FUNCTION prime */
110
111 int computeCar(int a, int n)
112 {
113 /* FUNCTION computeCar */
114 int success;
115 int exp;
116 unsigned long base;
117 unsigned long result;
118
119 /* a^n % n = a */
120
121 DEBUG printf("entere computeCar: a = %d n = %d\n", a, n);
122 base = a;
123 exp = n;
124 result = 1;
125 while (0 < exp)
126 {
127 /* while */
128 DEBUG printf("exp = %d result = %d base = %d n = %d a = %d\n", exp, result, base, n, a);
129 if (1 == (exp & 1))
130 {
131 /* this power is multiplied by base */
132 result = (result * base) % n;
133 } /* this power is multiplied by base */
134 exp = exp >> 1; /* divide by 2 */
135 base = (base * base) % n; /* caluculate next power */
136 } /* while */
137 DEBUG printf("exp = %d result = %d base = %d n = %d a = %d\n", exp, result, base, n, a);
138 exp = result;
139 DEBUG printf("n=%d exp = %d result=%d\n", n, exp, result);
140 return exp;
141 } /* FUNCTION computeCar */
142
143 int carTest(int n)
144 {
145 /* FUNCTION carTest */
146 int success;
147 int i;
148
149 success = (! prime(n));
150 for (i=0; (success) && (primes[i] <= n); i++)
151 /* for (i=2; (success) && (i < n); i++) */
152 {
153 /* for */
154 success = primes[i] == computeCar(primes[i], n);
155 } /* for */
156 return success;
157 } /* FUNCTION carTest */
158
159 void initCar()
160 {
161 /* FUNCTION initCar */
162 int success;
163 int i;
164 int j;
165 unsigned long tot;
166 int k;
167
168 /* a^n % n = a */
169 carCnt = 0;
170 for (k=2; k<MAX_SIZE; k++)
171 {
172 /* for k */
173 if (carTest(k))
174 {
175 DEBUG printf("car[%d] = %d\n", carCnt, k);
176 car[carCnt++] = k;
177 }
178 } /* for k */
179 } /* FUNCTION initCar */
180
181 void process()
182 {
183 /* FUNCTION process */
184 int i;
185 int match = FALSE;
186
187 for (i=0; (! match) && (i<carCnt); i++)
188 {
189 /* for */
190 match = car[i] == n;
191 } /* for */
192 if (match)
193 printf("The number %d is a Carmichael number.\n", n);
194 else
195 printf("%d is normal.\n", n);
196 } /* FUNCTION process */
197
198 int main()
199 {
200 /* main */
201 int moreToDo;
202
203 init();
204 initCar();
205 moreToDo = getInput();
206 while (moreToDo)
207 {
208 /* while */
209 process();
210 moreToDo = getInput();
211 } /* while */
212
213 return EXIT_SUCCESS;
214 } /* main */
215