Rabin-Miller Prime Test

// C++ program Miller-Rabin primality test
#include <bits/stdc++.h>
#define MAX 10000
#define long long long

using namespace std;
long mul(long a, long b, long mod) {
    long ans = 0;
    while (b) {
        if (b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}
long binByMod(long a, long to, long mod) {
    long ans = 1;
    while (to) {
        if (to & 1)
            ans = mul(ans, a, mod);
        a = mul(a, a, mod);
        to >>= 1;
    }
    return ans;
}
long randomLong() {
    long ans = 0;
    for (int i = 0; i < 4; ++i)
        ans = (ans << 16) ^ rand();
    return ans;
}

bool isPrime(long n) {
    if (n % 2 == 0 && n != 2||n==1)
        return false;
    for (int i = 0; i < 20; ++i) {
        long a = (randomLong() % (n - 1));
        if (a < 0)
            a += n - 1;
        a += 1;

        a = binByMod(a, (n - 1) / 2, n);
        if (a != n - 1 && a != 1)
            return false;
    }

    return true;
}
int main()
{

    long  n=1;
    if(isPrime(n))
        cout<<"PRIME"<<endl;
    else
        cout<<"NOT"<<endl;
    return 0;
}