my code is failing for only 1st testcase
i am using rabin miller
i even tried increasing the accuracy
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll power(ll a, ll b, ll mod)
{
ll res = 1;
while (b)
{
if (b & 1)
res = (res * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return res;
}
bool check(ll d, ll n)
{
ll a = 2+(rand()%(n-4));
ll x = power(a,d,n);
if(x==1 || x==n-1)
return true;
while(d!=n-1)
{
x=(x*x)%n;
if(x==1)
return false;
if(x==n-1)
return true;
d=(d*2);
}
return false;
}
bool primal(ll n)
{
if(n<=4)
{
if(n==2 || n==3)
return true;
return false;
}
if(n%2==0)
return false;
ll d = (n-1);
while(d%2==0)
d/=2;
ll accuracy = 4;
for(ll i=0;i<accuracy;i++)
{
if(!check(d,n))
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ll x,n;
cin >> x;
while(x--)
{
cin>>n;
if(primal(n))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}