src/math/millerrabin.hpp

• View this file on GitHub
• Last update: 2025-11-13 05:48:47+08:00
• Include: #include "src/math/millerrabin.hpp"

Depends on

• src/math/pow_mod_ll.hpp

Required by

• src/math/pollardrho.hpp
• src/math/proot.hpp

Verified with

• test/math/millerrabin.test.cpp
• test/math/pollardrho.test.cpp
• test/math/proot.test.cpp

Code

// 时间复杂度: $\mathcal{O}(k \log n)$，目前 $k = 9$ 足以判定 $64$ 位整数.
#include "pow_mod_ll.hpp"
bool isprime(ll n) {
  if (n < 2) return 0;
  int s = __builtin_ctzll(n - 1);
  ll d = (n - 1) >> s;
  for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
    if (a == n) return 1;
    ll x = pow_mod_ll(a, d, n);
    if (x == 1 || x == n - 1) continue;
    bool ok = 0;
    for (int i = 0; i + 1 < s; i++) {
      x = i128(x) * x % n;
      if (x == n - 1) {
        ok = 1;
        break;
      }
    }
    if (!ok) return 0;
  }
  return 1;
}

#line 1 "src/math/millerrabin.hpp"
// 时间复杂度: $\mathcal{O}(k \log n)$，目前 $k = 9$ 足以判定 $64$ 位整数.
#line 1 "src/math/pow_mod_ll.hpp"
ll pow_mod_ll(ll a, ull n, ll p) {
  ll ret = 1;
  for (; n; n /= 2) {
    if (n & 1) ret = i128(ret) * a % p;
    a = i128(a) * a % p;
  }
  return ret;
}
#line 3 "src/math/millerrabin.hpp"
bool isprime(ll n) {
  if (n < 2) return 0;
  int s = __builtin_ctzll(n - 1);
  ll d = (n - 1) >> s;
  for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
    if (a == n) return 1;
    ll x = pow_mod_ll(a, d, n);
    if (x == 1 || x == n - 1) continue;
    bool ok = 0;
    for (int i = 0; i + 1 < s; i++) {
      x = i128(x) * x % n;
      if (x == n - 1) {
        ok = 1;
        break;
      }
    }
    if (!ok) return 0;
  }
  return 1;
}

Back to top page