Nhập một số n,kiểm tra số n bằng phương pháp miller

#include <iostream>
using namespace std;

#define int __int128
template <class T>
void readInt(T& num) {
    num = 0;
    char c = getchar();
    while (c != '-' && ('0' > c || '9' < c)) c = getchar();
    bool neg = false;
    if (c == '-') neg = true, c = getchar();
    for(num = 0; '0' <= c && c <= '9'; c = getchar()) num = (num << 1) + (num << 3) + (c - '0');
    if (neg) num = -num;
}

template <class T>
istream& operator>>(istream& i, T& x) {
    readInt(x);
    return i;
}

ostream& operator<<(ostream& o, const __int128& x) {
    if (x < 0) return o << "-" << -x;
    if (x < 10) return o << (char)(x + '0');
    return o << x / 10 << (char)(x % 10 + '0');
}

/* ==================================== */

int power(int A, int N, int M) {
    int ret = 1; A = A % M;

    while (N > 0) {
        if (N & 1) ret = ret * A % M;
        N >>= 1;
        A = A * A % M;
    }

    return ret;
}

bool check(int A, int s, int d, int N) {
    if (N == A) return true;
    int p = power(A, d, N);
    if (p == 1) return true;

    for(; s > 0; s--) {
        if (p == N - 1) return true;
        p = p * p % N;
    }

    return false;
}

bool prime(int x) {
    if (x <= 1) return false;
    if (x % 2 == 0) return x == 2;
    if (x % 3 == 0) return x == 3;

    int d = x - 1, s = 0;
    while ((d & 1) == 0) {
        s++;
        d >>= 1;
    }

    for(int i: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
        if (!check(i, s, d, x)) return false;

    return true;
}

/* ====================================== */

signed main() {
    int n; cin >> n;
    cout << prime(n);
}