了解分解函数

Question

请注意,此问题包含一些剧透.

一个对问题排名第12的解决方案规定,

"除数(包括1和数字本身)可以从素数(和幂)除数中取一个元素来计算."

它执行此操作的(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

我希望你现在看到为什么我们在计算除数时将一个加到指数中.