約数列挙(Divisor)

説明

ある数の約数を列挙する。

計算量

• $O(\sqrt N)$

実装例

• divisor($n$):= $n$ の約数を返す。

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