UVa 10006 - Carmichael Numbers

// UVa 10006 - Carmichael Numbers
#include <iostream>
#include <cmath>
#include <string.h>

#define type unsigned long long

using namespace std;

bool prime[65000];

void findprimes() {
	memset(prime, true, sizeof(bool) * 65000);
	for (int i = 2; i < 65000; i++) {
		if (prime[i]) {
			for (int j = i + i; j < 65000; j += i)
				prime[j] = false;
		}
	}
}

type M(type a, type e, type n) {
	if (e == 1)
		return a % n;
	else {
		if (e % 2 == 0)
			return (type) (pow(M(a, e / 2, n) * 1.0, 2.0)) % n;
		else
			return (type) (pow(M(a, e / 2, n) * 1.0, 2.0)) * a % n;
	}
}

int main() {

	findprimes();

	type n;
	cin >> n;
	while (n != 0) {
		bool carmichael;

		if (prime[n])
			carmichael = false;
		else {

			carmichael = true;

			for (type a = 2; a < n; a++) {

				type mod = M(a, n, n);

				if (mod != a) {
					carmichael = false;
					break;
				}
			}
		}

		if (carmichael)
			cout << "The number " << n << " is a Carmichael number." << endl;
		else
			cout << n << " is normal." << endl;

		cin >> n;
	}

	return 0;
}