約数列挙
(algorithm/Math/NumberTheory/divisors.hpp)

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

概要

自然数 $n$ の約数を列挙する．

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

参考文献

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

Verified with

• verify/aoj-ITP1_3_D-divisors.test.cpp

Code

#ifndef ALGORITHM_DIVISORS_HPP
#define ALGORITHM_DIVISORS_HPP 1

#include <algorithm>
#include <cassert>
#include <map>
#include <vector>

namespace algorithm {

// 約数列挙．O(√N).
template <typename Type>
std::vector<Type> divisors(Type n) {
    assert(n >= 1);
    std::vector<Type> res;  // res[]:=(自然数nの約数の集合).
    for(Type p = 1; p * p <= n; ++p) {
        if(n % p == 0) {
            res.push_back(p);
            Type q = n / p;
            if(q != p) res.push_back(q);
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

// 高速約数列挙．
template <typename Type>
std::vector<Type> divisors(const std::map<Type, int> &pf) {
    std::vector<Type> res({1});
    for(const auto &[p, cnt] : pf) {
        const int sz = res.size();
        Type b = 1;
        for(int i = 0; i < cnt; ++i) {
            b *= p;
            for(int j = 0; j < sz; ++j) res.push_back(res[j] * b);
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

}  // namespace algorithm

#endif

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



#include <algorithm>
#include <cassert>
#include <map>
#include <vector>

namespace algorithm {

// 約数列挙．O(√N).
template <typename Type>
std::vector<Type> divisors(Type n) {
    assert(n >= 1);
    std::vector<Type> res;  // res[]:=(自然数nの約数の集合).
    for(Type p = 1; p * p <= n; ++p) {
        if(n % p == 0) {
            res.push_back(p);
            Type q = n / p;
            if(q != p) res.push_back(q);
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

// 高速約数列挙．
template <typename Type>
std::vector<Type> divisors(const std::map<Type, int> &pf) {
    std::vector<Type> res({1});
    for(const auto &[p, cnt] : pf) {
        const int sz = res.size();
        Type b = 1;
        for(int i = 0; i < cnt; ++i) {
            b *= p;
            for(int j = 0; j < sz; ++j) res.push_back(res[j] * b);
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

}  // namespace algorithm

Back to top page