python中給定數字的最大素數因子

我無法理解我遇到此網站本身的以下代碼塊。它創建一個函數來找出給定數字的最大素數因子。它下面給出：python中給定數字的最大素數因子

def prime_factors(n): 
"""Returns all the prime factors of a positive integer""" 
factors = [] 
d = 2 
while n > 1: 
    while n % d == 0: 
     factors.append(d) 
     n /= d 
    d = d + 1 

return factors 
pfs = prime_factors(1000) 
largest_prime_factor = max(pfs) # The largest element in the prime

我的疑問是，功能prime_factors(n)將返回因素n，而不是首要因素，因爲如果d是n因素while循環只檢查和不是如果它也是它應該是的主要。

請指出，如果我錯了，也是你的邏輯背後的推理。此外，如果我是正確的，那麼請簡單地提供一個合適的代碼塊及其背後的邏輯。儘量保持代碼儘可能簡單。

來源

2016-05-13 Aradhye Agarwal

這是我會怎麼解決這個問題。第一步：我會用例子運行程序，看它是否會產生因素或主要因素。第二步：當我發現我的猜測是錯誤的（程序確實按照廣告的方式工作）時，我會用小數字（n = 4，n = 6，n = 18可能是有趣的）自己運行程序，然後看看這是怎麼回事。 –

請注意，在內循環中，n在迭代時除以d。

while n % d == 0: 
    factors.append(d) 
    n /= d

這意味着，在每次迭代之後，這是不可能的n的新值是由d除盡了。

舉一個例子，比如說n = 3000，它有一個因子15這不是質數。然而，由於n由d = 3和d = 5通過第一，時間d達到15，n本來是一個數字，既不通過3也不5整除，因此非主要因素15現在不會通過n % d == 0。

來源

2016-05-13 04:48:35

非常感謝！另外，不是寫「n> 1」，我們不能寫「d <= n」來簡化事情嗎？ –

這個函數是正確的，注意第二個block。它將連續地將給定數字除以d變量，當除法結果有餘數時，它將離開該塊並將d增加1，然後它將再次運行。

考慮到這一點，這個函數會將數字除以2，並且不會留下餘數，然後它將移動到下一個不會留下餘數的數字。最終結果將只包含素數。

它會是這樣的：

def prime_factors(n): 
    factors = [] 
    d=2 
    while n > 1: 
    while n % d == 0: 
     factors.append(d) 
     n /= d 
    d += 1 
    return factors 

print(prime_factors(1000)) # will print [2, 2, 2, 5, 5, 5]

來源

2016-05-13 04:52:12

python中給定數字的最大素數因子

回答

相關問題