题解 | #【模板】Pollard-Pho算法#

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

using u128 = __uint128_t;
using u64 = unsigned long long;
using u32 = unsigned int;

u64 mul_mod(u64 a, u64 b, u64 mod) {
    return (u128)a * b % mod;
}

u64 pow_mod(u64 a, u64 d, u64 mod) {
    u64 r = 1;
    while (d) {
        if (d & 1) r = mul_mod(r, a, mod);
        a = mul_mod(a, a, mod);
        d >>= 1;
    }
    return r;
}

bool miller_rabin(u64 n) {
    if (n < 2) return false;
    for (u64 p : {2ull,3ull,5ull,7ull,11ull,13ull,17ull}) {
        if (n % p == 0) return n == p;
    }
    u64 d = n - 1, s = 0;
    while ((d & 1) == 0) { d >>= 1; ++s; }
    auto trial = [&](u64 a) -> bool {
        u64 x = pow_mod(a % n, d, n);
        if (x == 1 || x == n - 1) return true;
        for (u64 r = 1; r < s; ++r) {
            x = mul_mod(x, x, n);
            if (x == n - 1) return true;
        }
        return false;
    };
    for (u64 a : {2ull,3ull,5ull,7ull,11ull,13ull,17ull}) {
        if (!trial(a)) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        unsigned long long n; 
        cin >> n;
        cout << (miller_rabin(n) ? "Yes" : "No") << '\n';
    }
    return 0;
}

import java.io.*;
import java.math.BigInteger;

public class Main {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            do { c = read(); } while (c <= 32);
            while (c > 32) { sb.append((char)c); c = read(); }
            return sb.toString();
        }
        int nextInt() throws IOException { return Integer.parseInt(next()); }
    }

    static final long[] BASES = {2,3,5,7,11,13,17,19,23,29,31,37};

    static boolean isPrime(BigInteger n) {
        if (n.compareTo(BigInteger.valueOf(2)) < 0) return false;
        if (n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) return n.equals(BigInteger.valueOf(2));
        BigInteger d = n.subtract(BigInteger.ONE);
        int s = 0;
        while (d.and(BigInteger.ONE).equals(BigInteger.ZERO)) { d = d.shiftRight(1); s++; }
        for (long aLong : BASES) {
            if (BigInteger.valueOf(aLong).compareTo(n.subtract(BigInteger.ONE)) >= 0) continue;
            BigInteger a = BigInteger.valueOf(aLong);
            BigInteger x = a.modPow(d, n);
            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) continue;
            boolean pass = false;
            for (int r = 1; r < s; r++) {
                x = x.multiply(x).mod(n);
                if (x.equals(n.subtract(BigInteger.ONE))) { pass = true; break; }
            }
            if (!pass) return false;
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();
        int T = fs.nextInt();
        while (T-- > 0) {
            BigInteger n = new BigInteger(fs.next());
            out.append(isPrime(n) ? "Yes" : "No").append('\n');
        }
        System.out.print(out.toString());
    }
}

import sys

def is_probable_prime(n: int) -> bool:
    if n < 2:
        return False
    small_primes = [2, 3, 5, 7, 11, 13, 17]
    for p in small_primes:
        if n % p == 0:
            return n == p
    # write n-1 = d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    def trial(a: int) -> bool:
        x = pow(a % n, d, n)
        if x == 1 or x == n - 1:
            return True
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                return True
        return False
    for a in small_primes:
        if not trial(a):
            return False
    return True

data = sys.stdin.buffer.read().split()
it = iter(data)
T = int(next(it))
out_lines = []
for _ in range(T):
    n = int(next(it))
    out_lines.append('Yes' if is_probable_prime(n) else 'No')
sys.stdout.write('\n'.join(out_lines))