fermat's theorem (doesnt work on numbers less than three), but checks all primes in O((log(n)^2)

gistfile1.txt

boolean isPrime(long n)
{//fermats :D
  if (n%2==0 || n%3==0)
	{
		return false;
	}
	boolean res = true;
	for (long a = 2; a<n; a*=2)
	{
		res = res&&exp_mod_itr(a,n,n)==a;
	}
	return res;
}

long exp_mod_itr(long a, long b, long c)
{
	if (c==0)
	{
		return 0; //because you're clearly too stupid to do math
	}
	if (b==0)
	{
		return 1;
	}
	if (a==0)
	{
		return 0; //why are you even here
	}

	long result = a%c;
	int k = 1;

	while(b > k)
	{
		if ((b-k)%2==0 && k*2<=b)
		{
			result *= result;
			k *= 2;
		}
		else
		{
			result *= (a%c);
			k += 1;
		}
		result %= c;
	}
	return result;
}