题解 | 判断质数

Miller-Rabin素性检验（大炮轰蚊子）

#include <iostream>
#include <array>

using i64 = long long;

i64 mul(i64 a, i64 b, i64 m) {
  return static_cast<__int128>(a) * b % m;
}

i64 power(i64 a, i64 b, i64 m) {
  i64 res = 1 % m;
  for (; b; b >>= 1, a = mul(a, a, m))
    if (b & 1)
      res = mul(res, a, m);
  return res;
}

bool isprime(i64 n) {
  if (n < 2)
    return false;
  static constexpr std::array A = {2, 3, 5, 7, 11, 13, 17, 19, 23};
  int s = __builtin_ctzll(n - 1);
  i64 d = (n - 1) >> s;
  for (auto a : A) {
    if (a == n)
      return true;
    i64 x = power(a, d, n);
    if (x == 1 || x == n - 1)
      continue;
    bool ok = false;
    for (int i = 0; i < s - 1; ++i) {
      x = mul(x, x, n);
      if (x == n - 1) {
        ok = true;
        break;
      }
    }
    if (!ok)
      return false;
  }
  return true;
}

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

  i64 n;
  std::cin >> n;

  std::cout << (isprime(n) ? "Yes\n": "No\n");

  return 0;
}