/home/toolbox/public_html/solutions/100/10006/x.cpp
1 /*
2 * Sai Cheemalapati
3 * UVa 10006: Carmichael numbers
4 *
5 */
6
7 #include<bitset>
8 #include<cstdio>
9 #include<vector>
10
11 using namespace std;
12
13 int n;
14 bitset<10000010> bs;
15 bool is_prime[65100], is_carmichael[65100];
16
17 void sieve(long long upper_bound)
18 {
19 bs.set();
20 bs[0] = bs[1] = 0;
21 for (long long i = 2; i <= upper_bound + 1; i++)
22 {
23 if (bs[i])
24 {
25 for (long long j = i * i; j <= upper_bound + 1; j += i)
26 bs[j] = 0;
27 is_prime[i] = true;
28 }
29 }
30 }
31
32 int mod_pow(long long base, int exp, int mod)
33 {
34 long long result = 1;
35 while (exp > 0)
36 {
37 if (exp % 2 == 1)
38 result = (result * base) % mod;
39 exp = exp >> 1;
40 base = (base * base) % mod;
41 }
42 return result;
43 }
44
45 bool carmichael(int n)
46 {
47 if (is_prime[n]) return false;
48 for (int i = 2; i < n; i++)
49 {
50 if (mod_pow(i, n, n) != i) return false;
51 }
52 return true;
53 }
54
55 int main()
56 {
57 sieve(65000);
58 for (int i = 2; i <= 65000; i++)
59 is_carmichael[i] = carmichael(i);
60 for (;;)
61 {
62 scanf("%d", &n);
63 if (n == 0) break;
64
65 printf(is_carmichael[n]? "The number %d is a Carmichael number.\n" : "%d is normal.\n", n);
66 }
67 }
68