約数列挙

用途

与えられた自然数の約数を列挙する.

計算量

$ O(\sqrt{n}) $

使い方

例えばdivisor(12)をすると, vector<int>{1,2,3,4,6,12}が返ってくる. 昇順であることが保証される.

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
vector<int> divisor(int n) {
  vector<int> head, tail;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      head.push_back(i);
      if (i * i != n)
        tail.push_back(n / i);
    }
  }
  head.insert(head.end(), tail.rbegin(), tail.rend());
  return head;
}

Verify

//TODO