UVA10006 – Carmichael Numbers

题目链接：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;
}