number_of_divisors

関数 · 素因数分解

// (1)
std::uint64_t number_of_divisors(std::vector<std::uint64_t> v);

// (2)
std::uint64_t number_of_divisors(std::uint64_t n);

概要

(1) 素因数列 v から元の整数の正の約数個数を返す

v は重複を含んでよく、関数内で整列される。

• 計算量: 素因数の個数を $k$ として $O(k\log k)$

(2) 整数 n の正の約数個数を返す

• 計算量: 素因数分解により期待 $O(n^{1/4}\log n)$

関連項目

• factorize — 素因数分解
• primitive_root — 原始根