Тест Миллера — Рабина

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
#include <cmath>
#include <algorithm>
#include <chrono>

using namespace std;

#define ll long long

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll mod;

ll add(ll a, ll b) { return (a + b) % mod; }

ll mul(ll a, ll b) {
    ll ret = 0;
    while (b) {
        if (!(b & 1))
            a = add(a, a), b >>= 1;
        ret = add(ret, a), --b;
    }

    return ret;
};

ll get(ll n, ll m) {
    ll ret = 1;
    while (m) {
        if (!(m & 1))
            n = mul(n, n), m >>= 1;
        ret = mul(ret, n), --m;
    }

    return ret;
}

ll prec[63];

bool stress(ll n) {
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0)
            return false;
    }
    return true;
}

void brik() {
    cout << "NO";
    exit(0);
}

void sech() {
    if ((double)clock() / CLOCKS_PER_SEC > 1.9) {
        cout << "YES";
        exit(0);
    }
}

void $main()
{
    prec[0] = 1;
    for (ll i = 1; i < 63; ++i)
        prec[i] = (prec[i - 1] << 1);

    cin >> mod;

    if (mod == 2)
    {
        cout << "YES";
        exit(0);
    }

    if ((mod & 1) == 0 || mod == 1) {
        brik();
    }

    ll d = mod - 1, s = 0;
    while ((d & 1) == 0)
        ++s, d >>= 1;

    while (true) {
        sech();

        ll a = rng() % mod;
        if (!a)++a;

        ll cur = get(a, d);
        if (cur == 1 || cur == -1)
            continue;

        bool fl = 0;
        for (ll i = 0; i < s; ++i) {
            sech();

            cur = mul(cur, cur);
            if (cur == 1 || cur == -1) {
                fl = true;
                break;
            }
        }

        if (!fl)
            brik();
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    $main();

    return 0;
}