N の約数を全列挙するアルゴリズム

2020年3月4日数学約数,競プロ,全列挙

整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。

単純なアルゴリズムでは約数の全列挙に \(O(N)\) だけかかりますが、約数の性質を活かすと \(O(\sqrt{N})\) で全列挙することが可能です。

アルゴリズム

単純なアルゴリズム：

  1. 1 から N まで以下を繰り返す
    • N を割り切れたら約数として保存する

※ 1 から N まで全探索して、全ての約数を列挙します

効率的なアルゴリズム：

  1. d=1 から \(\lfloor \sqrt{N} \rfloor\) まで以下を繰り返す
    • N を割り切れたら、d と \(\frac{N}{d}\) を約数として保存する

※ d が N の約数と分かった場合、\(\frac{N}{d}\) もN の約数だと分かります。この性質を利用すると 1 から \(\sqrt{N}\) までを探索すれば良いです。

計算量

  • 単純なアルゴリズム：\(O(N)\)
  • 効率的なアルゴリズム：\(O(\sqrt{N})\)

単純なアルゴリズムでは、1 から N まで全ての数を確かめるので、計算量は \(O(N)\) になります。

効率的なアルゴリズムでは、1 から \(\sqrt{N}\) まで全ての数を確かめるので、計算量は \(O(\sqrt{N})\) になります。

C++ での実装例

単純なアルゴリズム

/*  divisor(n)
    入力：整数 n
    出力：nのすべての約数
    計算量：O(N)
*/
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(n / i);
        }
    }
    return ret;
}

効率的なアルゴリズム

d=\(\sqrt{N}\) が整数の場合は、\(\frac{N}{d} = \frac{N}{\sqrt{N}}\) も同じく \(\sqrt{N}\) になるので重複して数えないようにする必要があります。

また、約数を昇順に並べて出力したい場合は、以下のように結果をソートする必要があるでしょう。（ソートを行うと \(O(\sqrt{N})\) を少し超えてしまいます。\(\frac{N}{d}\) の部分は別の配列に保存しておき、最後に並び順を反転してからつなげると \(O(\sqrt{N})\) で昇順に並べることが可能です。）

/*  divisor(n)
    入力：整数 n
    出力：nのすべての約数
    計算量：O(√n)
*/
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}

練習問題

数学約数,競プロ,全列挙