I am given prime factorization of a number as a map: std::map<int, int> m, where key is a prime number, and value is how many times this prime number occured in product.
Example: Prime factorization of 100 is 2 * 2 * 5 *5, so m[2] = 2, and m[5] = 2
My question is how can I get number of all divisors of a number given it's prime factorization (in the form as above)?
CodePudding user response：
Number of divisors is simply equal to product of counts of every prime plus 1.
This comes from the fact that you can easily restore all divisors by having several nested loops iterating through all combinations of powers of primes. Every loop iterates through powers of single prime.
Number of different iterations of nested loops equal to product of sizes of all loops. And size of each loop is equal to prime count plus one, because you iterate through powers 0, 1, 2, ..., PrimeCnt, which has PrimeCnt 1 numbers.
For example for 100 = 2 * 2 * 5 * 5 you have m[2] = 2 and m[5] = 2, hence you want to combine all powers of 2 with all powers of 5, i.e. combined 2^0 or 2^1 or 2^2 (here are 3 powers) with 5^0 or 5^1 or 5^2 (here are 3 powers), hence 3 powers multiplied by 3 powers gives 9.
This also can be easily verified by simple program below, which first computes all divisors as product of PrimeCnt 1, and afterwards verifies this fact by computing all divisors through iteration.
You can easily put any number n and map of primes m into program below to verify other cases.
#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;
}
Output:
Computed as product: 9
Computed through iteration: 9
CodePudding user response：
All divisors of 7².11³.61 are of the form 7^u.11^v.61^w, with 0≤u≤2, 0≤v≤3 and 0≤w≤1. Thus there are (2 1).(3 1).(1 1) combinations. Observe the pattern.