c++ - 质因数分解的除数

Question

我得到一个数字的质因数分解作为映射:std::map<int, int> m ，其中key是一个质数，value是这个质数在product中出现的次数。

示例:100 的质因数分解为 2 * 2 * 5 *5，所以 m[2] = 2 , 和 m[5] = 2

我的问题是，如果一个数是质因数分解(如上所示)，我如何才能得到它的所有除数？

Answer 1

除数的数量等于每个素数的计数乘积加 1。

这是因为您可以通过多个嵌套循环遍历素数幂的所有组合来轻松恢复所有除数。每个循环都遍历单个素数的幂。

嵌套循环的不同迭代次数等于所有循环大小的乘积。每个循环的大小等于素数加一，因为您遍历 0, 1, 2, ..., PrimeCnt 的幂，它有 PrimeCnt + 1 个数.

例如 100 = 2 * 2 * 5 * 5 你有 m[2] = 2 和 m[5] = 2，因此你想将 2 的所有幂与 5 的所有幂组合，即将 2^0 或 2^1 或 2^2(这里有 3 个幂)与 5^0 或 5^1 或 5^2(此处是 3 次幂)，因此 3 次幂乘以 3 次幂得到 9。

这也可以通过下面的简单程序轻松验证，该程序首先计算所有除数作为 PrimeCnt + 1 的乘积，然后通过迭代计算所有除数来验证这一事实。

您可以轻松地将任意数字 n 和质数映射 m 放入下面的程序中以验证其他情况。

Try it online!

#include <iostream>
#include <map>

int main() {
    int n = 100;
    std::map<int, int> m = {{2, 2}, {5, 2}};
    int c = 1;
    for (auto [k, v]: m)
        c *= v + 1;
    std::cout << "Computed as product: " << c << std::endl;
    int c2 = 0;
    for (int i = 1; i <= n; ++i)
        if (n % i == 0)
            ++c2;
    std::cout << "Computed through iteration: " << c2 << std::endl;
}

输出:

Computed as product: 9
Computed through iteration: 9