【競プロ用】約数列挙、素数判定、素因数分解、素数列挙（エラトステネスのふるい）のC++テンプレート

競プロ用に約数、素数関連のよく使う処理をテンプレ化したので、そのメモ ※追加後にいくつかバグが見つかっています。ご利用の際は自己責任でお願いしますm( )m

// 約数列挙
vector<ll> get_divs(ll n) {
  vector<ll> res;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      if (i * i == n) {
        res.push_back(i);
      } else {
        res.push_back(i);
        res.push_back(n / i);
      }
    }
  }
  return res;
}

// 素数判定
bool is_prime(ll n) {
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

// 素因数分解
map<ll, int> get_primes(ll x) {
  map<ll, int> res;
  for (ll i = 2; i * i <= x; i++) {
    while (x % i == 0) {
      res[i] += 1;
      x /= i;
    }
  }
  // 最後に残った数を追加
  if (x != 1) {
    res[x] += 1;
  }
  return res;
}

// 素数列挙（エラトステネスのふるい）
vector<int> era_primes(ll n) {
  vector<int> res(n + 1, 1);  // 素数なら1, それ以外は0
  res[0] = 0;
  res[1] = 0;

  for (ll i = 2; i * i <= n; i++) {
    ll x = 2 * i;
    // 素数じゃないものに印をつける
    while (x <= n) {
      if (res[x]) {
        res[x] = 0;
      }
      x += i;
    }
  }
  return res;
}