約数列挙

コード例

C++

using ll = long long;

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

TypeScript

function divisor(n: number): number[] {
  let ret: number[] = [];
  for (let i = 1; i * i <= n; i++) {
    if (n % i === 0) {
      ret.push(i);
      if (i * i !== n) {
        ret.push(n / i);
      }
    }
  }
  return ret;
}

アルゴリズム

正の整数 N の約数を求める場合、 1 ～ N の各値で割り切れるかどうかを確かめればいいのだが、もう少し効率のいい方法を考えてみる。

ある整数 a が N の約数だとわかる場合、 N / a の値も約数になる。

例えば 3 が 12 の約数だということがわかると、 12 / 3 = 4 で 4 も同時に約数だということがわかる。

a の値として考えられるのが、重複することを考えると、 1 からスタートして、 N まで見る必要は無い。

実際には 1 から $\sqrt{N}$ まで見ればいいことがわかっている。

なぜなら、 N = a x b で、 a <= b が成り立つとき、 a が $\sqrt{N}$ より大きいと、 b も $\sqrt{N}$ より大きくなるので、 a x b が N を超えてしまう。

100 = 10 x 10 のように、 a と b が重複している場合は、片方だけを列挙するように調整する点も注意する必要がある。

具体的な例を挙げてみる。

100 の約数を求める場合、 100 = ab の a の範囲は 1 から $\sqrt{100}$ 、つまり 1 ～ 10 になる。

• 100 を 1 で割り切ることができるので、 1 と (100/1 である) 100 のペアが約数
• 100 を 2 で割り切ることができるので、 2 と (100/2 である) 50 のペアが約数
• 100 を 3 で割り切ることはできない
• 100 を 4 で割り切ることができるので、 4 と (100/4 である) 25 のペアが約数
• 100 を 5 で割り切ることができるので、 5 と (100/5 である) 20 のペアが約数
• 100 を 6 で割り切ることはできない
• 100 を 7 で割り切ることはできない
• 100 を 8 で割り切ることはできない
• 100 を 9 で割り切ることはできない
• 100 を 10 で割り切ることができるので、 10 が約数

これで 100 の約数は 1, 2, 4, 5, 10, 20, 25, 50, 100 の 9 個だとわかる。

計算量

1 から $\sqrt{N}$ まで割り切れるかを確かめるので、計算量は $O(\sqrt{N})$ になる。