python - 了解因式分解函数

Question

请注意，这个问题包含一些剧透。

A solution for problem #12指出

"Number of divisors (including 1 and the number itself) can be calculated taking one element from prime (and power) divisors."

它执行此操作的(python)代码是num_factors = lambda x: mul((exp+1) for (base, exp) in factorize(x))(其中 mul() 是 reduce(operator.mul, ...)。)

它没有说明 factorize 是如何定义的，我很难理解它是如何工作的。它如何告诉您数字的因数个数？

Answer 1

基本思想是，如果您将一个数字分解为以下形式，这实际上是标准形式:

let p be a prime and e be the exponent of the prime:

N = p1^e1 * p2^e2 *....* pk^ek

现在，要知道 N 有多少个除数，我们必须考虑质因数的每种组合。所以你可以说除数的数量是:

e1 * e2 * e3 *...* ek

但您必须注意，如果其中一个质因数的标准形式的指数为零，那么结果也将是一个除数。这意味着，我们必须为每个指数加一，以确保我们将第 i 个 p 包含在零的幂中。这是一个使用数字 12 的示例——与问题编号相同 :D

Let N = 12
Then, the prime factors are:
2^2 * 3^1
The divisors are the multiplicative combinations of these factors. Then, we have:
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12

我希望您现在明白为什么我们在计算除数时要在指数上加一。