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