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

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

(async function(){
    const N = Number(await readline());
    for(let i=0;i<N;i++){
        console.log(isPrime(BigInt(await readline()))?'Yes':'No');
    }
})()
.finally(()=>rl.close());
const isPrime = (n) => {
  if (n < 2n) return false;
  if (n % 2n === 0n) return n === 2n;
  if (n % 3n === 0n) return n === 3n;

  let d = n - 1n;
  let s = 0;
  while ((d & 1n) === 0n) s++, d >>= 1n;

  const pow = (a, e, m) => {
    let r = 1n;
    for (; e; e >>= 1n) {
      if (e & 1n) r = (r * a) % m;
      a = (a * a) % m;
    }
    return r;
  };

  const test = (a) => {
    let x = pow(a, d, n);
    if (x === 1n || x === n - 1n) return true;
    for (let i = 0; i < s - 1; i++) {
      x = (x * x) % n;
      if (x === n - 1n) return true;
    }
    return false;
  };

  const bases = [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n];
  for (const a of bases) {
    if (a >= n) break;
    if (!test(a)) return false;
  }
  return true;
};