2016-01-22 104 views
0

參考:項目歐拉#3 Python中

的13195是5,7,13和29 號碼是多少600851475143的最大質因數的首要因素是什麼?

所以我解決了項目歐拉的第三個問題後,一點點的修補。不是最典型的代碼,但它大多是有效的。

import math 
import itertools 

def is_prime(x): 
    # Checks if the factor is prime. If not, breaks and looks at the next one 
    split_tuple = math.modf(math.sqrt(x)) 
    max_prime_div_possible = int(split_tuple[1]) 
    prime = True 
    for i in range(2, max_prime_div_possible+1): 
     if x % i == 0: 
      prime = False 
      break 
     else: 
      pass 
    return prime 

def factor_me(x): 
    # Creates a list of all factors of a number 
    factors = [] 
    split_tuple = math.modf(math.sqrt(x)) 
    max_pf_possible = int(split_tuple[1]) 
    for i in xrange(2, max_pf_possible+1): 
     if x % i == 0: 
      factors.append(i) 
      x = x/i 
     else: 
      pass 

    # Checks each factor for prime-ity, and if it is, sets it as the max prime factor. 
    for j in factors: 
     if is_prime(j) == True: 
      max_prime_factor = j 
     else: 
      pass 
    return max_prime_factor 


print factor_me(600851475143) # works correctly 
print factor_me(6008514751435) # fails 

的事情是,即使代碼工作正常與兩個例子測試,並提出問題,如果另一個數字被添加到數被因式分解,代碼休息。舉個例子來說明一下,取6008514751435.
根據Wolfram Alpha的說法,這個因素分解爲5,7和171671850041.然而,根據我的代碼,最大的因子是7.所以,我很難過。有什麼建議麼?

回答

0

您只檢查原始數字(6008514751435)的平方根,即2451227.因爲最終因子大於此值(171671850041),因此它永遠不會被添加到factors。不管x什麼時候迴路耗盡,如果它不是1,是最後一個因素。您也可以停止檢查一次x等於1

for i in xrange(2, max_pf_possible+1): 
    if x % i == 0: 
     factors.append(i) 
     x = x/i 
     if x == 1: break # Check that all factors found. 
else: 
    factors.append(x) 

如果你不familar與for/elseelse只執行,如果for循環排出。來自循環的break將跳過else

+0

廢話,否:代碼是我對#3問題的解決方案。但我的意思是,即使將n設置爲6008514751435,代碼也會出現一個7. 爲了清楚起見,讓我快速更改。 編輯:改變。 – matacusa

+0

@matacusa,我打錯了。我寫了'600851475143'而不是'6008514751435',但平方根和失敗的原因仍然是正確的。 –

+0

嗯,我現在明白了。但是,如果最大素因子可能高於數的平方根,是否是蠻力的唯一選擇?我想象這麼長時間的這麼多人。 – matacusa