素因数分解 (prime factorization)
(include/emthrm/math/prime_factorization.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/prime_factorization.hpp"

時間計算量

$O(\sqrt{N})$

仕様

名前	戻り値
template <typename T> std::vector<std::pair<T, int>> prime_factorization(T n);	$n$ の素因数分解

参考文献

• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，p.111，マイナビ出版（2012）

TODO

• ポラード・ロー素因数分解法 (Pollard’s rho algorithm)
  • https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95
  • https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
  • https://mathtrain.jp/rhoalgorithm
  • http://joisino.hatenablog.com/entry/2017/08/03/210000
  • http://idm.s9.xrea.com/factorization/rho.html
  • https://wacchoz.hatenablog.com/entry/2019/01/05/230128
  • https://gist.github.com/vintersnow/b0fa0faeef7597eba33400d2e615ad0e
  • http://orolog.hatenablog.jp/entry/20100804/1280943541
  • https://qiita.com/gushwell/items/561afde2e00bf3380c98
  • https://github.com/ei1333/library/blob/master/math/fast-prime-factorization.cpp
  • https://mugen1337.github.io/procon/Math/PollardRho.cpp
  • https://sotanishy.github.io/cp-library-cpp/math/fast_prime.cpp
  • https://judge.yosupo.jp/problem/factorize

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/NTL_1_A/review/4088167/emthrm/C++14

Required by

• 原始根 (primitive root) 判定 (include/emthrm/math/is_primitive_root.hpp)

Verified with

• ゲーム/ニム (test/game/nim.test.cpp)
• 数学/原始根判定 (test/math/is_primitive_root.test.cpp)
• 数学/素因数分解 (test/math/prime_factorization.test.cpp)

Code

#ifndef EMTHRM_MATH_PRIME_FACTORIZATION_HPP_
#define EMTHRM_MATH_PRIME_FACTORIZATION_HPP_

#include <utility>
#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::pair<T, int>> prime_factorization(T n) {
  std::vector<std::pair<T, int>> res;
  for (T i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      int exponent = 0;
      for (; n % i == 0; n /= i) {
        ++exponent;
      }
      res.emplace_back(i, exponent);
    }
  }
  if (n > 1) res.emplace_back(n, 1);
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_PRIME_FACTORIZATION_HPP_

#line 1 "include/emthrm/math/prime_factorization.hpp"



#include <utility>
#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::pair<T, int>> prime_factorization(T n) {
  std::vector<std::pair<T, int>> res;
  for (T i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      int exponent = 0;
      for (; n % i == 0; n /= i) {
        ++exponent;
      }
      res.emplace_back(i, exponent);
    }
  }
  if (n > 1) res.emplace_back(n, 1);
  return res;
}

}  // namespace emthrm

Back to top page