prime_factorization

関数 · 素数列挙・判定

std::vector<std::pair<std::uint64_t, int>> prime_factorization(std::uint64_t x);

概要

素因数分解

戻り値

(素数, 指数) のペアを素数の昇順で列挙したもの

計算量

• Pollard’s rho により期待 $O(x^{1/4}\log x)$

関連項目

• is_prime — 素数判定
• divisors — 約数列挙
• multiplicative_partitions — 乗法的分割
• Sieve — 素数の篩