如何通过质因数分解的std::map<int, int>求正整数的约数个数？

云原生阿岚

2026-8-13

如何通过质因数分解结果计算正整数的约数个数？

核心原理

这用的是约数个数定理：如果一个正整数的质因数分解为 ( n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k} )（其中 ( p_i ) 是质数，( a_i ) 是该质数在分解式中的出现次数），那它的所有约数个数就是把每个质数的出现次数加1后，再相乘的结果，也就是：
[ (a_1 + 1) \times (a_2 + 1) \times ... \times (a_k + 1) ]
加1的原因很简单：每个质数在约数里可以选0次、1次……直到它的最大出现次数，总共就是 ( a_i + 1 ) 种选择，所有质数的选择组合起来就是总约数数量。

结合std::map的实现方式

拿到存储质因数的std::map<int, int>后，只需要遍历这个map，把每个键对应的值（质数的出现次数）加1，再把所有结果累乘即可。

用C++代码实现的示例：

#include <map>

int countDivisors(const std::map<int, int>& factorMap) {
    int result = 1;
    for (const auto& pair : factorMap) {
        result *= (pair.second + 1);
    }
    return result;
}