Рабин для гениев

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

#define cerr if (false) cerr
#define int unsigned long long


namespace Miller {
    int p;
    vector<int> need = {2, 3, 5, 7, 11, 17, 21, 27, 29};

    int binmul(int a, int b) {
        int ans = 0;
        while (b) {
            if (b & 1) {
                ans += a;
                ans %= p;
            }
            b >>= 1;
            if (b) {
                a += a;
                a %= p;
            }
        }
        return ans;
    }


    int binpow(int a, int b) {
        int ans = 1;
        while (b) {
            if (b & 1) {
                ans = binmul(ans, a);
            }
            b >>= 1;
            if (b) {
                a = binmul(a, a);
            }
        }
        return ans;
    }

    int tr(int a) {
        int q = p - 1;
        while (q % 2 == 0) {
            q /= 2;
        }
        int cp = q;
        int cur = binpow(a, cp);
        if (cur == 1 || cur == p - 1) {
            return 1;
        }
        while (cp < p - 1) {
            cp *= 2;
            cur = binmul(cur, cur);
            if (cur == p - 1) {
                return 1;
            }
        }
        return 0;
    }

    int solve(int x) {
        if (x == 1) {
            return 0;
        }
        p = x;
        for (auto t : need) {
            if (t == x) {
                return 1;
            }
            if (gcd(t, x) > 1) {
                return 0;
            }
            bool cr = tr(t);
            //cout << t << ' ' << cr << endl;
            if (!cr) {
                return 0;
            }
        }
        //cout << "RETURN 1" << endl;
        return 1;
    }
} //namespace Miller

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    assert(freopen("again.in", "r", stdin));
    assert(freopen("again.out", "w", stdout));

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        bool tmp = Miller::solve(x);
        if (tmp) {
            cout << "YES" << endl;
        }  else {
            cout << "NO" << endl;
        }
    }

    // Miller::p = 1e9 + 239;
    // cout << Miller::binmul(5, 7) << endl;
}