Prime Factor (素因数分解) (math/number-theory/prime-factor.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/prime-factor.hpp"

prime_factor

map< int64_t, int > prime_factor(int64_t n)

$n$ を素因数分解した結果を連想配列で返します。連想配列の添字は素因数、値は指数です。

制約

• $0 \le n$

計算量

• $O(\sqrt n)$

Verified with

• test/verify/aoj-ntl-1-a.test.cpp

Code

#pragma once

#include <cstdint>
#include <map>

std::map<std::int64_t, int> prime_factor(std::int64_t n) {
  std::map<std::int64_t, int> ret;
  for (std::int64_t i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

#line 2 "math/number-theory/prime-factor.hpp"

#include <cstdint>
#include <map>

std::map<std::int64_t, int> prime_factor(std::int64_t n) {
  std::map<std::int64_t, int> ret;
  for (std::int64_t i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

Back to top page