Divisor (約数)
(math/prime/divisor.hpp)

• View this file on GitHub
• Last update: 2020-04-22 00:08:28+09:00
• Include: #include "math/prime/divisor.hpp"

概要

約数を列挙する. ソートはされていない.

計算量

$O(\sqrt{n})$

使用例

• divisor(N) : $N$の約数を返す.
  • 返り値の型 : vector<long long>

Verified with

• test/yukicoder/888.test.cpp

Code

/**
 * @brief Divisor (約数)
 * @docs docs/math/prime/divisor.md
 */

vector<long long> divisor(const long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            ret.emplace_back(i);
            if (i * i != n) ret.emplace_back(n / i);
        }
    }
    return ret;
}

#line 1 "math/prime/divisor.hpp"
/**
 * @brief Divisor (約数)
 * @docs docs/math/prime/divisor.md
 */

vector<long long> divisor(const long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            ret.emplace_back(i);
            if (i * i != n) ret.emplace_back(n / i);
        }
    }
    return ret;
}

Back to top page