题解 | 判断质数

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

i128 qpow(i128 a, i128 b, i128 mod) {//Miller Rabin模板代码 检验一个很大的数字是否为质数 记下来即可 无需理解
    i128 ret = 1;
    while(b) {
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret % mod;
}

i128 p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
int p_cnt = 12;

bool miller_rabin(i128 n) {
    if(n < 3 || n % 2 == 0) return n == 2;
    i128 u = n - 1;
    int t = 0;
    while(u % 2 == 0) u /= 2, ++ t;
    for(int i = 0; i < p_cnt; i ++) {
        i128 a = p[i];
        if(n == a) return true;
        if(n % a == 0) return false;
        i128 v = qpow(a, u, n);
        if(v == 1) continue;
        
        bool found = false;
        for(int s = 1; s <= t; s ++) {
            if(v == n - 1) {
                found = true;
                break;
            }
            v = v * v % n;
        }
        if(!found) return false;
    }
    return true;
}

void solve() {
    long long x;
    cin >> x;
    i128 n = x;
    if(miller_rabin(n)) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}