TLE in PON using Fermat's Little Theorem

[nerdap]

I'm trying to use Fermat's Little Theorem to solve PON, but I can't get past the time limit. It times out even when I have K = 1 (K is the number of iterations). I've also tried using the gcd algorithm to make my solution run faster (to ensure that a and n are coprime).

Here's my code:

#include <cstdlib>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
const int K = 2;
ull gcd(ull a, ull b)
{
	static ull c;
	while(a != 0)
	{
		c = a;
		a = b % a;
		b = c;
	}
	return b;
}
ull powmod(ull a, ull e, ull m)
{
	// computes (a^e) % m
	ull c = 1, eprime = 0;
	while(eprime < e)
	{
		eprime++;
		c = (a*c) % m;
	}
	return c;
}
bool isPrime(ull n)
{
	for(int i = 0; i < K; i++)
	{
		ull a;
		do
		{
			a = rand() % (n - 1) + 1;
		}while(gcd(a, n) != 1);
		if(powmod(a, n - 1, n) != 1)
			return false;
	}
	return true;
}
int main()
{
    int t;

scanf("%d", &t);
for(int i = 0; i < t; i++)
{
	ull n;
	
	scanf("%lld", &n);
	if(isPrime(n))
		printf("YES\n");

	else
		printf("NO\n");
}
return 0;
}

Can anyone tell me what I can do to make my program faster? Will Miller-Rabin be a better algorithm to work with here?

[nerdap]

bump

[leppyr64]

do
{
    a = rand() % (n - 1) + 1;
}while(gcd(a, n) != 1);

Can you tell me for certain how many iterations this will take? The answer is no. That's why you're exceeding the timelimit.

Rabin-Miller tends to be a common one that I hear around here.