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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/number-theory/prime-factor.hpp"

prime_factor

map< int64_t, int > prime_factor(int64_t n)

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

制約

• $0 \le n$

計算量

• $O(\sqrt n)$

Verified with

• test/verify/aoj-ntl-1-a.test.cpp

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