Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

:heavy_check_mark: Prime Factor(素因数分解)
(math/number-theory/prime-factor.hpp)

prime_factor

map< int64_t, int > prime_factor(int64_t n)

$n$ を素因数分解した結果を連想配列で返します。連想配列の添字は素因数、値は指数です。

制約

計算量

Verified with

Code

map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}
#line 1 "math/number-theory/prime-factor.hpp"
map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}
Back to top page