Divisor(約数列挙)
(math/number-theory/divisor.hpp)

• View this file on GitHub
• Last update: 2022-10-23 20:41:53+09:00
• Include: #include "math/number-theory/divisor.hpp"

与えられた整数の約数を列挙します。

divisor

vector< int64_t > divisor(int64_t n)

n の約数を昇順に返します。

制約

• $1 \le n$

計算量

• $O(\sqrt n)$

Verified with

• test/verify/aoj-itp1-3-d.test.cpp

Code

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;
}

#line 1 "math/number-theory/divisor.hpp"
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;
}

Back to top page