Spoj PON Solution

 #include<bits/stdc++.h>

#define ll unsigned long long int

using namespace std;

ll base[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

ll mod(ll a, ll b, ll m)

{

    ll r = 0;

    a = a%m;

    while(b > 0)

    {

        if(b&1)

            r = (r+a)%m;

        b = b >> 1;

        a = (a+a)%m;

    }

    return r;

}

ll power(ll a, ll d, ll n)

{

    ll r = 1;

    a = a%n;

    while(d > 0)

    {

        if(d&1) // d%2 == 1

            r = mod(r, a, n);

        d = d >> 1; // d = d/2;

        a = mod(a, a, n);

    }

    return r;

}

bool check(ll a, ll d, ll n)

{

    ll x = power(a, d, n);

    if(x == 1 || x == n-1)

        return true;

    while(d != n-1)

    {

        x = mod(x, x, n);

        d = (d << 1); // d = d * 2

        if(x == 1)

            return false;

        if(x == n-1)

            return true;

    }

    return false;

}

bool miller_robin(ll n)

{

    ll d = n-1;

    while(d%2 == 0)

        d = d/2;

    for(int i=0; i<12; i++)

    {

        if(base[i] == n)

            return true;

        if(check(base[i], d, n) == false)

            return false;

    }

    return true;

}

int main()

{

    int t;

    cin >> t;

    while(t--)

    {

        ll n;

        cin >> n;

        if((n <= 1 || n%2 == 0) && n != 2)

            cout << "NO" << "\n";

        else if(n <= 3)

            cout << "YES" << "\n";

        else

        {

            if(miller_robin(n))

                cout << "YES" << "\n";

            else

                cout << "NO" << "\n";

        }

    }

    return 0;

}