题目链接：UVA10006
本来想直接打素数表，然后根据素数表来判断，结果一直超时，后来把素数表去掉，再在for循环中加判断才勉强过了。
Some numbers that are not prime still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers.
只要按着这两个条件判断即可。
具体看代码：
#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
bool isPrimer(int num);
int powerMode(int,int,int);
//bool primeTable[65010];
int main()
{
// for(int i=1;i<=65010;i++)
// if(isPrimer(i))
// primeTable[i]=1; //素数标为1
// else
// primeTable[i]=0;
int number;
while(cin>>number,number!=0)
{
bool flag=0;
// not prime
if(isPrimer(number))
flag=1;
// pass the Fermat test with every
// number smaller than themselves.
//Let a be a random number between 2 and n - 1
for(int i=2;(i<number)&&!flag;i++)
if(powerMode(i,number,number)!=i)
flag=1; if(flag)
cout<<number<<" is normal."<<endl;
else
cout<<"The number "<<number<<" is a Carmichael number."<<endl;
}
return 0;
}
bool isPrimer(int number)
{
if(number<=2)
return true;
if(number%2==0)
return false;
for(int i=3;i<=ceil(sqrt(number));i++)
if(number%i==0)
return false;
return true;
}
//计算 pow(a,n)%n=a
int powerMode(int a,int n,int mode)
{
long long answer=1;
while(n)
{
if(n&1)
answer=(answer*a)%mode;
a=((long long )a*a)%mode;
n=n>>1;
}
return answer;
}