miller.cpp

#include <cstdio>
using namespace std;
typedef struct miller_test{
    long long mul(long long a, long long b, long long M){
        long long r = 0;
        while (b)
        {
            if (b & 1)
            {
                r += a;
                if (r>M) r -= M;
            }
            b >>= 1;
            a <<= 1;
            if (a>M) a -= M;
        }
        return r;
    }
    long long pow(long long a, long long b, long long M){
        long long r = 1;
        while (b)
        {
            if (b & 1) r = mul(r, a, M);
            b >>= 1;
            a = mul(a, a, M);
        }
        return r;
    }
    bool miller_rabin(long long a, long long n){
        if (a >= n) return true;
        long long r = 0, s = n - 1, j;
        while (!(s & 1)) s >>= 1, r++;
        long long x = pow(a, s, n);
        if (x == 1) return true;
        for (j = 0; j<r; j++, x = mul(x, x, n)) if (x == n - 1) return true;
        return false;
    }
    bool isprime(long long n){
        if (n == 1)
            return false;
        int base[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
        for (int i = 0; i<5; i++) if (!miller_rabin(base[i], n)) return false;
        return true;
    }
}miller_test;
int main(){
    long long N; scanf("%lld", &N);
    miller_test Miller;
    Miller.isprime(N);//if prime number..return 1
}