理解factorize函数

Question

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

一个关于第12题的解决方案提到：

“一个数的因子个数（包括1和这个数本身）可以通过取出它的质因数（和它们的幂）来计算。”

这个（python）代码是 num_factors = lambda x: mul((exp+1) for (base, exp) in factorize(x)) （其中 mul() 是 reduce(operator.mul, ...)）。

但是它没有说明 factorize 是怎么定义的，我对它的工作原理有些困惑。它是怎么告诉你一个数有多少个因子的呢？

Answer 1

我不是Python专家，但如果你想计算一个数字的因子个数，你需要先把这个数字进行质因数分解。

这个公式很简单：你要把每个质因数的指数加一，然后把这些结果相乘。

举几个例子：

12 = 2^2 * 3^1 -> 这里的指数是2和1，加一后变成3和2，3乘以2等于6，所以12有6个因子（1, 2, 3, 4, 6, 12）。

30 = 2^1 * 3^1 * 5^1 -> 这里的指数都是1，加一后都是2，2乘以2乘以2等于8，所以30有8个因子（1, 2, 3, 5, 6, 10, 15, 30）。

40 = 2^3 * 5^1 -> 这里的指数是3和1，加一后变成4和2，4乘以2等于8，所以40有8个因子（1, 2, 4, 5, 8, 10, 20, 40）。

Answer 2

基本的想法是，如果你有一个数字，它可以分解成以下的标准形式：

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

但是你要注意，如果某个质因数在标准形式中的指数是零，那么这个结果也会是一个因数。这意味着，我们需要在每个指数上加一，以确保我们包括了 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

我希望你现在明白了为什么在计算因数时要在指数上加一。