给你一个数，让你判断这个数是不是 Carmichael 数。对于一个数，如果满足：
1. 这个数不是素数。
2. 对于 2 <= a < n，有 a^n\\ mod\\ n \\neq a。

简单的数论题，直接根据条件来判断。先筛素数，再用快速幂运算来判断第二个条件。

#include <bits/stdc++.h>
using namespace std;
const int N = 65005;
int prime[N];
void init()
{
  memset(prime, -1, sizeof(prime));
  prime[1] = 0;
  for (int i = 2; i < N; i++) {
    if (prime[i]) {
      for (int j = i + i; j < N; j += i) {
        prime[j] = 0;
      }
    }
  }
}
inline int power(int n, int k, int m)
{
  int res = 1;
  while (k) {
    if (k & 1) {
      res = 1LL * res * n % m;
    }
    n = 1LL * n * n % m;
    k >>= 1;
  }
  return res;
}
int main()
{
  int n;
  init();
  while (~scanf("%d", &n) && n) {
    if (prime[n]) {
      printf("%d is normal.\n", n);
      continue;
    }
    int a;
    for (a = 2; a < n; a++) {
      if (power(a, n, n) != a) {
        break;
      }
    }
    if (a >= n) {
      printf("The number %d is a Carmichael number.\n", n);
    } else {
      printf("%d is normal.\n", n);
    }
  }
  return 0;
}