2010-07-17 92 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