/home/toolbox/public_html/solutions/100/10006/c.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
37 */
38
39 #define MAX_PRIMES 6600
40 #define MAX_SIZE 65005
41
42 int n;
43
44 int buff[MAX_SIZE];
45
46 void init()
47 {
48 /* FUNCTION init */
49 int i;
50 int j;
51
52 buff[0] = 0;
53 buff[1] = 0;
54 buff[2] = 2;
55
56 /* sieve of erasthones */
57 for (i=3; i<MAX_SIZE; i=i+2)
58 {
59 buff[i]=i;
60 buff[i+1]=0;
61 }
62 for (i=3; i<MAX_SIZE; i=i+2)
63 {
64 /* loop through primes */
65 if (0 != buff[i])
66 {
67 /* found a prime */
68 DEBUG printf("%d\n", i);
69 for (j=i+i+i; j<MAX_SIZE; j=j+i+i)
70 {
71 /* mark out multiples */
72 buff[j] = 0;
73 } /* mark out multiples */
74 } /* found a prime */
75 } /* loop through primes */
76 } /* FUNCTION init */
77
78 void dump()
79 {
80 /* FUNCTION dump */
81 } /* FUNCTION dump */
82
83 int getInput()
84 {
85 /* FUNCTION getInput */
86 int dataReadFlag;
87
88 scanf(" %d ", &n);
89 dataReadFlag = (0 != n);
90 return (dataReadFlag);
91 } /* FUNCTION getInput */
92
93 int prime(int x)
94 {
95 /* FUNCTION prime */
96 return (0 != buff[x]);
97 } /* FUNCTION prime */
98
99 void process()
100 {
101 /* FUNCTION process */
102 int success = TRUE;
103 int i;
104 int j;
105 unsigned long tot;
106
107 /* a^n % n = a */
108 if (prime(n))
109 {
110 /* number is prime, no need to test */
111 success = FALSE;
112 } /* number is prime, no need to test */
113 else
114 {
115 /* non prime -- check it */
116 for (i=2; (success) && (i<n); i++)
117 {
118 /* try each number less than n */
119 if (0 != buff[i])
120 {
121 tot = 1;
122 for (j=0; j<n; j++)
123 {
124 /* multiply n times */
125 DEBUG printf("i(%d) j(%d) tot = %d\n", i, j, tot);
126 tot = (tot * i) % n;
127 } /* multiply n times */
128 DEBUG printf("n(%d) i(%d) tot = %d\n", n, i, tot);
129 success = success && (i == tot);
130 }
131 } /* try each number less than n */
132 } /* non prime -- check it */
133 if (success)
134 printf("The number %d is a Carmichael number.\n", n);
135 else
136 printf("%d is normal.\n", n);
137 } /* FUNCTION process */
138
139 int main()
140 {
141 /* main */
142 int moreToDo;
143
144 init();
145 moreToDo = getInput();
146 while (moreToDo)
147 {
148 /* while */
149 process();
150 moreToDo = getInput();
151 } /* while */
152
153 return EXIT_SUCCESS;
154 } /* main */
155