約数列挙
(library/number/divisors.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/number/divisors.hpp"

約数列挙

できること

• 整数Nの約数一覧の配列を返す

計算量

$O(\sqrt N)$

使い方

vector<int> divs = divisors(N);

Verified with

• 約数列挙のテスト (tests/number.divisors.test.cpp)
• エラトステネスの篩のテスト (tests/number.prime.eratosthenes.test.cpp)

Code

#pragma once
vector<int> divisors(int N) {
    vector<int> res;
    for (int i = 1; i * i <= N; ++i) {
        if (N % i != 0) continue;
        res.push_back(i);
        if (N / i != i) res.push_back(N / i);
    }
    return res;
}

#line 2 "library/number/divisors.hpp"
vector<int> divisors(int N) {
    vector<int> res;
    for (int i = 1; i * i <= N; ++i) {
        if (N % i != 0) continue;
        res.push_back(i);
        if (N / i != i) res.push_back(N / i);
    }
    return res;
}

Back to top page