==== 소감 ====
{{| 2005/05/09 Accepted 0:02.826 452 |}}

중간에 발생하는 버그를 잡는데 대부분의 시간을 허비했다. 65000 이란 수는 작지만 65000의 제곱은 int형의 범위를 벗어난다. ㅡㅡ; 오버플로우를 교모히 이용한 함정에 고생했다. 
Carmichael Numbers를 찾는 Theorem이 있는 듯하다. 그러나 때려맞추기(?)로 문제를 풀어도 풀린다. 그러나 속도는 떨어진다.

==== 코드 ====
{{{~cpp 
// no10006 - Carmichael Numbers
#include <iostream>
#include <cmath>
using namespace std;

const int NORMAL = 1;
const int CARMICHAEL = 2;

bool isPrime(int n);
void show(int n, int type);
bool isCarmichael(int n);
bool passFermatTest(int a, int n);
int findModulo(unsigned int a, unsigned int n);

int main()
{
	int n;			// n = input integer ( 2 < n < 65,000)
	while (cin >> n && n != 0)
	{
		if (isPrime(n))
		{
			show(n, NORMAL);
			continue;
		}
		if (isCarmichael(n))
			show(n, CARMICHAEL);
		else
			show(n, NORMAL);
	}		
	return 0;
}

bool isPrime(int n)
{
	for (int i = 3; i <= sqrt(n) + 1; i += 2)
		if (n % i == 0)
			return false;
	return true;
}

void show(int n, int type)
{
	if (type == NORMAL)
		cout << n << " is normal.\n";
	else
		cout << "The number " << n << " is a Carmichael number.\n";
}

bool isCarmichael(int n)
{
	for (int i = 2; i <= n - 1; i++)
	{
		if (!passFermatTest(i, n))
			return false;
	}
	return true;
}

bool passFermatTest(int a, int n)
{	
	int modulo = findModulo(a, n);
	if (modulo == a)
		return true;
	return false;
}

int findModulo(unsigned int a, unsigned int n)
{
	unsigned int modN = n;
	unsigned int expo = 2;
	unsigned int mod = (a * a) % n;
	unsigned int modulo = 1;
	while (1)
	{
		while (expo * 2 <= modN)
		{
			expo *= 2;
			mod = (mod * mod) % n;
		}
		
		if (modN - expo <= 6)
		{	
			for (int i=0; i < modN-expo; i++) 
			{
				mod = (mod * a) % n;
			}
			break;
		}

		else
		{
			modulo = (modulo * mod) % n;
			modN -= expo;
			expo = 2;
			mod = (a * a) % n;			
		}
	}
	return (modulo * mod) % n;
}
}}}
----
[CarmichaelNumbers] [AOI]