fermat.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

mt19937 rd(random_device{}());

ll mul(ll a, ll b, ll c)
{
	return __int128(a)*b%c;
}

ll expo(ll a, ll p, ll m)
{
	ll t = 1;

	while(p)
	{
		if(p & 1) t = mul(t, a , m);
		a = mul(a, a, m);
		p >>= 1;
	}
	return t;
}

bool checaprimalidade(int n, int iteracoes)
{
	if(n < 4) return n == 2 || n == 3;

	while(iteracoes--)
	{
		ll a = 2 + rd()%(n - 3);

		if(expo(a, n - 1, n) != 1) return false;
		
	}
	return true;
}