素因数分解してmapに格納する関数

素因数分解する問題が出てきた＋次回同じものを書くのが面倒なのでスニペット化するついでに共有。

main.cpp

template<typename T, typename U>
void primeFactorization(map<T, U> &primes, T N) {
  T n = N;
  U num = 0;
  while (n%2 == 0) {
    num++;
    n /= 2;
  }
  if (num != 0) {
    primes.emplace(2, num);
  }

  for (T i = 3; i*i <= N; i += 2) {
    num = 0;

    while (n%i == 0) {
      num++;
      n /= i;
    }
    if (num != 0) {
      primes.emplace(i, num);
    }

  }

  /* √Nより大きい値の素数が存在する場合nが1にならないので最後に追加 */
  if (n != 1) {
    primes.emplace(n, 1);
  }
}


int main(void) {
  /* 使用例 */
  long long N; cin >> N;
  map<long long, int> p;
  primeFactorization(p, N);
  
  return 0;
}

使いどころさん！

ABC169 D - Div Game 問題 + 回答例