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++ での実装例

単純なアルゴリズム

効率的なアルゴリズム

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

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

練習問題

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