素因数分解
(algorithm/Math/NumberTheory/prime_factorize.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/NumberTheory/prime_factorize.hpp"

概要

自然数 $n$ に対して素因数分解を行う．

本実装では「試し割り法 (trial division)」を用いており，計算量は $\mathcal{O}(\sqrt n)$ となる．

参考文献

1. “試し割り法”. Wikipedia. https://ja.wikipedia.org/wiki/試し割り法.

Verified with

• verify/aoj-NTL_1_A-prime_factorize.test.cpp

Code

#ifndef ALGORITHM_PRIME_FACTORIZE_HPP
#define ALGORITHM_PRIME_FACTORIZE_HPP 1

#include <cassert>
#include <map>

namespace algorithm {

// 素因数分解．O(√N).
template <typename Type>
std::map<Type, int> prime_factorize(Type n) {
    assert(n >= 0);
    std::map<Type, int> res;  // res[p]:=(自然数nに含まれる素因数pの個数).
    for(; n % 2 == 0; n /= 2) res[2]++;
    for(Type p = 3; p * p <= n; p += 2) {
        for(; n % p == 0; n /= p) res[p]++;
    }
    if(n > 1) res[n] = 1;
    return res;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/NumberTheory/prime_factorize.hpp"



#include <cassert>
#include <map>

namespace algorithm {

// 素因数分解．O(√N).
template <typename Type>
std::map<Type, int> prime_factorize(Type n) {
    assert(n >= 0);
    std::map<Type, int> res;  // res[p]:=(自然数nに含まれる素因数pの個数).
    for(; n % 2 == 0; n /= 2) res[2]++;
    for(Type p = 3; p * p <= n; p += 2) {
        for(; n % p == 0; n /= p) res[p]++;
    }
    if(n > 1) res[n] = 1;
    return res;
}

}  // namespace algorithm

Back to top page