Prime Factor (素因数分解)
(math/prime/prime_factor.hpp)

• View this file on GitHub
• Last update: 2020-04-21 22:55:01+09:00
• Include: #include "math/prime/prime_factor.hpp"

概要

素因数分解する.

計算量

$O(\sqrt{n})$

使用例

• prime_factor(N) : $N$を素因数分解したものを返す.
  • 返り値の型 : map<long long, int>

Verified with

• test/aoj/NTL_1_A.test.cpp

Code

/**
 * @brief Prime Factor (素因数分解)
 * @docs docs/math/prime/prime_factor.md
 */

map<long long, int> prime_factor(long long n) {
    map<long long, int> ret;
    for (long long 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/prime/prime_factor.hpp"
/**
 * @brief Prime Factor (素因数分解)
 * @docs docs/math/prime/prime_factor.md
 */

map<long long, int> prime_factor(long long n) {
    map<long long, int> ret;
    for (long long 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