factorize-trial-division (試し割りによる素因数分解)
(lib/factorize-trial-division.hpp)

• View this file on GitHub
• Last update: 2021-10-06 03:41:28+09:00
• Include: #include "lib/factorize-trial-division.hpp"

概要

TBD

使い方

TBD

計算量

TBD

Verified with

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

Code

/**
 * @brief factorize-trial-division (試し割りによる素因数分解)
 * @docs docs/factorize-trial-division.md
 */
template<typename T = int>
std::map<T, int> factorize(T n) {
    std::map<T, int> factor_map;
    for (T i = 2; i * i <= n; i++) {
        while (!(n % i)) {
            factor_map[i]++; n /= i;
        }
    }
    if (n > 1) factor_map[n]++;
    return factor_map;
}

#line 1 "lib/factorize-trial-division.hpp"
/**
 * @brief factorize-trial-division (試し割りによる素因数分解)
 * @docs docs/factorize-trial-division.md
 */
template<typename T = int>
std::map<T, int> factorize(T n) {
    std::map<T, int> factor_map;
    for (T i = 2; i * i <= n; i++) {
        while (!(n % i)) {
            factor_map[i]++; n /= i;
        }
    }
    if (n > 1) factor_map[n]++;
    return factor_map;
}

Back to top page