2010-07-17 51 views
4

请注意,此问题包含一些破坏者。了解分解函数

solution for problem #12指出

“除数(包括1和号码自身)的数量,可以计算考虑一个元件与素(和功率)的除数。”

的(蟒蛇),该公司已经在做这个代码是num_factors = lambda x: mul((exp+1) for (base, exp) in factorize(x))(其中mul()reduce(operator.mul, ...)

它没有说明factorize是如何定义的,和我无法理解它是如何工作的。它如何告诉你数字的因素数量?

回答

12

的基本想法是,如果你有分解成以下形式的数这是标准的形式实际上:

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 

但是你要注意的是,如果主要因素之一的标准形式的指数是零,那么结果也将是一个约数。这意味着,我们必须为每个指数添加一个,以确保我们包含第零个幂的零。下面是使用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 

我希望你现在明白为什么我们在计算除数时添加一个指数。

+0

谢谢!它现在非常有意义。只要它让我接受,就会接受。 – Daenyth 2010-07-17 21:47:47

+0

这是错误的。您必须首先为每个指数添加一个以获得正确的结果(请参阅我的解决方案)。 – Landei 2010-07-17 21:51:44

+3

@Landei请再次阅读答案,我解释了为什么我们需要添加一个实际。 “这意味着,我们必须为每个指数添加一个以确保我们包含第零个幂的零点” – AraK 2010-07-17 21:53:33

2

我不是Python专家,但是要计算除数的数量,您需要数字的素因式分解。公式很简单:您可以将每个素数除数的指数加一,然后将它们相乘。

实例:

12 = 2^2 * 3^1 - >指数为2和1,加一为3和2,3 * 2 = 6个除数(1,2,3,4,6 ,12)

30 = 2^1 * 3^1 * 5^1 - >指数是1,1和1,加1是2,2和2,2 * 2 * 2 = 8除数,2,3,5,6,10,15,30)

40 = 2^3 * 5^1 - >指数是3和1,加1是4和2,4 * 2 = 8除数( 1,2,4,5,8,10,20,40)

+0

什么是允许您确定指数的一般公式? – dominic 2010-12-10 16:31:31

+0

您必须因数分解,AFAIK没有其他方式来确定指数。 – Landei 2010-12-11 08:14:37