主要因素蟒噩夢

Question

一直試圖讓蟒蛇返回一個數字的最高首要因素，並敲打我明明榆木腦袋的11天后我已經準備好尋求幫助。任何想法爲什麼這不會返回最高的主要因素？它需要這麼長時間我手動退出程序，或抱怨說「蟒蛇詮釋大轉換爲C長」。任何幫助或建議將非常感謝！謝謝！

def primeCheck(value): 
    for x in range(2, int(value/2) + 1): 
     if value % x < 0.1: 
      return False 
    return True 

val = int(raw_input('What number would you like the highest prime factor of?')) 
pc = 2 
for x in xrange(pc, int((val/pc) + 1)): 
    if primeCheck(x) and val % x < 0.1: 
     val = val/x 
     pc = x 
print pc 

Answer 1

你的素性測試可能會好得多。根據您需要測試的數量有多大，您可以保留一大堆。這是一個nice collection of primes。更好的方式是像米勒 - 拉賓適當的測試，看看my code該作品到非常大的限制確定性版本。

你也可以看看真正的integer factorization算法。

Answer 2

怪我只是讀一個可愛解決這個今天 - 在這裏你去：

Tryptych's answer

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 = pfs[-1] # The largest (last) element in the prime factor array