素因数分解

1
vector<pair<int, int>> primeFactorize(int n) {
2
  vector<pair<int, int>> res;
3
  for (int a = 2; a * a <= n; ++a) {
4
    if (n % a == 0) {
5
      res.push_back({a, 0});
6
      while (n % a == 0)
7
        ++res.back().second, n /= a;
8
    }
9
  }
10
  if (n != 1)
11
    res.push_back({n, 1});
12
  return res;
13
}