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

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+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