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

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 06:54:42+00: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

#pragma once

#include <algorithm>
#include <cstdint>
#include <vector>

std::vector<std::int64_t> divisor(std::int64_t n) {
  std::vector<std::int64_t> ret;
  for (std::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);
    }
  }
  std::sort(ret.begin(), ret.end());
  return ret;
}

#line 2 "math/number-theory/divisor.hpp"

#include <algorithm>
#include <cstdint>
#include <vector>

std::vector<std::int64_t> divisor(std::int64_t n) {
  std::vector<std::int64_t> ret;
  for (std::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);
    }
  }
  std::sort(ret.begin(), ret.end());
  return ret;
}

Back to top page