/home/toolbox/public_html/solutions/100/10006/b.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 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 void initCar()
112 {
113 /* FUNCTION initCar */
114 int success;
115 int i;
116 int j;
117 unsigned long tot;
118 unsigned long base;
119 int k;
120
121 /* a^n % n = a */
122 carCnt = 0;
123 for (k=2; k<MAX_SIZE; k++)
124 {
125 /* for k */
126 if (prime(k))
127 {
128 /* number is prime, no need to test */
129 success = FALSE;
130 } /* number is prime, no need to test */
131 else
132 {
133 /* non prime -- check it */
134 success = TRUE;
135 for (i=0; (success) && (primes[i]<k); i++)
136 {
137 /* try each number less than n */
138 tot = 1;
139 j = k;
140 base = primes[i];
141 while (j > 0)
142 {
143 /* while */
144 if (1 == (j % 2))
145 {
146 tot = (tot * base) % k;
147 }
148 j >> 1;
149 base = (base * base) % k;
150 } /* while */
151
152 success = success && (primes[i] == tot);
153 } /* try each number less than n */
154 } /* non prime -- check it */
155 if (success)
156 {
157 printf("car[%d] = %d\n", carCnt, k);
158 car[carCnt++] = k;
159 }
160 } /* for k */
161 } /* FUNCTION initCar */
162
163 void process()
164 {
165 /* FUNCTION process */
166 int i;
167 int match = FALSE;
168
169 for (i=0; (! match) && (i<carCnt); i++)
170 {
171 /* for */
172 match = car[i] == n;
173 } /* for */
174 if (match)
175 printf("The number %d is a Carmichael number.\n", n);
176 else
177 printf("%d is normal.\n", n);
178 } /* FUNCTION process */
179
180 int main()
181 {
182 /* main */
183 int moreToDo;
184
185 init();
186 initCar();
187 moreToDo = getInput();
188 while (moreToDo)
189 {
190 /* while */
191 process();
192 moreToDo = getInput();
193 } /* while */
194
195 return EXIT_SUCCESS;
196 } /* main */
197