Primes

prime.cpp

#include <bits/stdc++.h>
#define ll long long
#define FASTIO   \
  cin.tie(NULL); \
  ios::sync_with_stdio(false);
#define END return 0;
#define out cout <<
#define in cin >>
#define i128 __int128
#define ui64 uint64_t
#define u128 __uint128_t
using namespace std;
ostream& operator<<(ostream& os, i128 x) {
  if (x == 0) {
    os << '0';
    return os;
  }
  if (x < 0) {
    os << '-';
    x = -x;
  }
  string s;
  while (x > 0) {
    s.push_back('0' + x % 10);
    x /= 10;
  }
  reverse(s.begin(), s.end());
  os << s;
  return os;
}
ll modmul(ll a, ll b, ll m) { return (i128)a * b % m; }
ll modpow(ll a, ll n, ll m) {
  ll r = 1;
  while (n) {
    if (n & 1) r = modmul(r, a, m);
    a = modmul(a, a, m);
    n >>= 1;
  }
  return r;
}
vector<ll> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
bool miller(ll n) {
  if (n < 2) return false;
  for (ll p : primes)
    if (n % p == 0) return n == p;
  ll d = n - 1, s = 0;
  while ((d & 1) == 0) {
    d >>= 1;
    s++;
  }
  for (ll a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
    if (a % n == 0) continue;
    ll x = modpow(a, d, n);
    if (x == 1 || x == n - 1) continue;
    bool flag = true;
    for (int r = 1; r < s; r++) {
      x = modmul(x, x, n);
      if (x == n - 1) {
        flag = false;
        break;
      }
    }
    if (flag) return false;
  }
  return true;
}
ui64 seed = chrono::steady_clock::now().time_since_epoch().count();
ui64 splitmix64() {
  uint64_t z = (seed += 0x9e3779b97f4a7c15);
  z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
  z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
  return z ^ (z >> 31);
}
ll rnd(ll l, ll r) { return l + splitmix64() % (r - l + 1); }
ll pollard(ll n) {
  if (n % 2 == 0) return 2;
  while (true) {
    ll x = rnd(2, n - 2);
    ll y = x;
    ll c = rnd(1, n - 1);
    ll d = 1;
    auto f = [&](ll x) { return (modmul(x, x, n) + c) % n; };
    while (d == 1) {
      x = f(x);
      y = f(f(y));
      d = gcd(llabs(x - y), n);
    }
    if (d != n) return d;
  }
}
void factor(ll n, vector<ll>& res) {
  if (n == 1) return;
  if (miller(n)) {
    res.push_back(n);
  } else {
    ll d = pollard(n);
    factor(d, res);
    factor(n / d, res);
  }
}
int main() {
  FASTIO

  END
}