素因数分解的因数数

Question

我得到了一个数字的素因数分解作为映射：

std::map<int, int> m

，其中键是一个素数，值是这个素数在乘积中出现的次数。

示例：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

放入下面的程序中以验证其他情况。

在线尝试！

#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

Answer 2

7².11³.61 的所有约数均为 7^u.11^v.61^w 形式，其中 0≤u≤2、0≤v≤3 和 0≤w≤1。因此有(2+1).(3+1).(1+1)种组合。观察图案。

Answer 3

要以映射的形式获取给定素因数分解的数字的所有约数的数量，可以使用以下公式：

除数数 = (m[p1] + 1) * (m[p2] + 1) * ... * (m[p n] + 1) 其中 p1, p2, ..., p n 是数字的质因数，m[pi] 是质因数 pi 在质因数分解中出现的次数。

#include <iostream>
#include <map>

using namespace std;

int countDivisors(const map<int, int>& primeFactorization) {
 int numDivisors = 1;
 for (const auto& pair : primeFactorization) {
    numDivisors *= (pair.second + 1);
 }
 return numDivisors;
}
int main() {
 map<int, int>primeFactorization = {{2, 2}, {5, 2}};
 int numDivisors = countDivisors(primeFactorization);
 cout<< "Number of divisors: " << numDivisors << endl;
 return 0;
}