10006 Carmichael Numbers

 ////=====BIsmillahir Rahmanir Rahim =====////

/*                        ______

 _______   /\     |``\   |        |  /

    |     /  \    |__/   |____    |/

    |    / _ _\   |  \   |        |\

    |   /      \  |   \  |______  |  \

            Dept. of CSE

         Comilla University

*/

#include<bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>

// #include <ext/pb_ds/tree_policy.hpp>

// #include <ext/pb_ds/detail/standard_policies.hpp>

#define fi 2*acos(0.0)

#define ee 2.71828

#define ll  long long

#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define Node struct node

#define spc " "

#define  E  2.71828182845904523536

#define pb push_back

#define pp pop_back

#define ff first

#define ss second

#define valid(nx,ny) nx>=0 && nx<n && ny>=0 && ny<m

#define edl printf("\n")

#define infinity 1e16

#define mod 1000000007

#define cn continue

#define csprint1 printf("Case %lld: ", cs++)

#define csprint2 printf("Case %lld:\n", cs++)

#define sf(a) scanf("%lld", &a)

#define sff(a,b) scanf("%lld %lld",&a,&b)

#define sfff(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define sffff(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)

#define all(v) v.begin(),v.end()

#define pfn(a) printf("%lld\n",a)

#define pfs(a) printf("%lld ",a)

// using namespace __gnu_pbds;

using namespace std;

typedef pair<ll, ll> pl;

typedef vector<int> vi;

typedef vector<pl> vpi;

typedef vector<pl> vpl;

// typedef tree<pair<ll, int> , null_type, less<pair<ll, int> >, rb_tree_tag, tree_order_statistics_node_update> ost;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}

template<typename T, typename... Args>

void err(istream_iterator<string> it, T a, Args... args)

{

    cerr << *it << " = " << a <<","<< spc;

    err(++it, args...);

    cout<<edl;

}

///Bit manipulation

bool checkbit(int mask,int bit){return mask & (1<<bit);}

int setbit(int mask,int bit){ return mask | (1<<bit) ; }

int clearbit(int mask,int bit){return mask & ~(1<<bit);}

int togglebit(int mask,int bit){return mask ^ (1<<bit);}

int bitno(int mask) {return (int)__builtin_popcount(mask);}

/*----------------------Graph Moves----------------*/

const int fx[]={+1,-1,+0,+0};

const int fy[]={+0,+0,+1,-1};

//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move

//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move

//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

/*------------------------------------------------*/

///=====================================///

const long long maX=65010;

bool flag[maX];        

bool charmical[maX]; 

void cal(){

    for(ll i=4;i<maX;i+=2)flag[i]=true;

    for(ll i=3;i*i<maX;i+=2){

        if(!flag[i]){

            for(ll j=i*i;j<maX;j+=2*i)flag[j]=true;

        }

    }

}            

ll exp(ll a,ll b,ll c){

    if(b==0)return 1;

    ll x=exp(a,b/2,c);

    x=(x*x)%c;

    if(b&1)x=(a*x)%c;

    return x%c;

}

int check(ll n){

    for(ll i=2;i<n;i++){

        if(exp(i,n,n) != i)return 0;

    }

    return 1;

}

int main(){

    FIO;

    cal();

    ll n;

    while(sf(n) && n){

        if(flag[n] && check(n))printf("The number %lld is a Carmichael number.\n",n);

        else printf("%lld is normal.\n",n);

    }

return 0;

}