UVa - 10006 - Carmichael Numbers

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#define mx 65000
using namespace std;
bool sample[mx];
int main(){
    for(int i = 2; i <= sqrt(mx); i++)
        if(sample[i] == 0)
            for(int j = i+i; j < mx; j += i)sample[j] = 1;
    int number;
    while(scanf("%d", &number) == 1){
        if(number == 0)break;
        int cnt = 0;
        for(int i = 2; i < mx; i++){
            if((sample[i] == 0) && (number % i == 0))
                if((number-1) % (i-1) == 0)cnt++;
            if(cnt == 3)break;
        }
        if(cnt == 3)printf("The number %d is a Carmichael number.\n", number);
        else printf("%d is normal.\n", number);
    }

    return 0;
}