尋找最大素因子（最快程序可能）

Question

我被檢查的http://projecteuler.net/

的問題，第三個問題是：

的13195的首要因素是5，7，13和29.最大的 數字600851475143的主要因素是什麼？

我的解決方案代碼如下。但是，我認爲這需要數週才能完成，所以速度非常緩慢。 我該如何改進它？或者是Python本身太慢而無法解決這個問題？

def IsPrime(num): 
    if num < 2: 
     return False 
    if num == 2: 
     return True 
    else: 
     for div in range(2,num): 
      if num % div == 0: 
       return False 
     return True 

GetInput = int (input ("Enter the number: ")) 


PrimeDivisors = [] 

for i in range(GetInput, 1, -1): 
    print(i) 
    if GetInput % i == 0 and IsPrime(i) is True: 
     PrimeDivisors.append(i) 
     break 
    else: 
     continue 


print(PrimeDivisors) 
print("The greatest prime divisor is:", max(PrimeDivisors)) 

Answer 1

與解決方案的問題是，你不坐你發現主要因素，所以你實際上找到最大的因素後，不必要地檢查因素。這裏是我的解決方案：

def largest_prime_factor(n): 
    largest = None 

    for i in range(2, n): 
     while n % i == 0: 
      largest = i 
      n //= i 

     if n == 1: 
      return largest 

    if n > 1: 
     return n 

項目歐拉的問題更多的是關於數學不是編程，因此，如果您的解決方案是太慢了，它可能不是你的語言，是有過錯的。

請注意，我的解決方案偶然爲這個特定的數字工作，所以它絕對不是一個通用的解決方案。更快的解決方案are complicated和在這種特定情況下的矯枉過正。

Answer 2

這可能不是最快的算法，但它是相當有效：

def prime(x): 
    if x in [0, 1]: 
     return False 
    for n in xrange(2, int(x ** 0.5 + 1)): 
     if x % n == 0: 
      return False 
    return True 

def primes(): 
    """Prime Number Generator 

    Generator an infinite sequence of primes 

    http://stackoverflow.com/questions/567222/simple-prime-generator-in-python 
    """ 

    # Maps composites to primes witnessing their compositeness. 
    # This is memory efficient, as the sieve is not "run forward" 
    # indefinitely, but only as long as required by the current 
    # number being tested. 
    # 
    D = {} 

    # The running integer that's checked for primeness 
    q = 2 

    while True: 
     if q not in D: 
      # q is a new prime. 
      # Yield it and mark its first multiple that isn't 
      # already marked in previous iterations 
      # 
      yield q   
      D[q * q] = [q] 
     else: 
      # q is composite. D[q] is the list of primes that 
      # divide it. Since we've reached q, we no longer 
      # need it in the map, but we'll mark the next 
      # multiples of its witnesses to prepare for larger 
      # numbers 
      # 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q] 

     q += 1 

def primefactors(x): 
    if x in [0, 1]: 
     yield x 
    elif prime(x): 
     yield x 
    else: 
     for n in primes(): 
      if x % n == 0: 
       yield n 
       break 
     for factor in primefactors(x // n): 
      yield factor 

用法：

>>> list(primefactors(100)) 
[2, 2, 5, 5] 

Answer 3

我的代碼似乎對我來說足夠快。使用collections.defaultdict（）會使primes（）的代碼變得更清晰，但我猜測代碼會因爲導入而失去一些速度。

def primes(): 
    """Prime number generator.""" 
    n, skip = 2, {} 
    while True: 
     primes = skip.get(n) 
     if primes: 
      for p in primes: 
       skip.setdefault(n + p, set()).add(p) 
      del skip[n] 
     else: 
      yield n 
      skip[n * n] = {n} 
     n += 1 

def un_factor(n): 
    """Does an unique prime factorization on n. 

    Returns an ordered tuple of (prime, prime_powers).""" 
    if n == 1: 
     return() 
    result = [] 
    for p in primes(): 
     (div, mod), power = divmod(n, p), 1 
     while mod == 0: 
      if div == 1: 
       result.append((p, power)) 
       return tuple(result) 
      n = div 
      div, mod = divmod(n, p) 
      if mod != 0: 
       result.append((p, power)) 
      power += 1 

試運行：

>>> un_factor(13195) 
((5, 1), (7, 1), (13, 1), (29, 1)) 
>>> un_factor(600851475143) 
((71, 1), (839, 1), (1471, 1), (6857, 1)) 
>>> un_factor(20) 
((2, 2), (5, 1)) 

編輯：素數小修改（）的基礎上this配方發電機。

EDIT2：固定爲20

EDIT3：代替greatest_prime_divisor（）與un_factor（）。

Answer 4

def getLargestFactor(n): 
    maxFactor = sqrt(n) 
    lastFactor = n 
    while n%2 == 0: 
     n /= 2 
     lastFactor = 2 
    for i in xrange(3,int(maxFactor),2): 
     if sqrt(n) < i: 
      return n 
     while n%i == 0 and n > 1: 
      n /= i 
      lastFactor = i 
    return lastFactor 

這應該是相當有效的。把每個因素全部分開，這樣我們只能找到主要因素。並且使用這樣一個事實，即只能有一個大於sqrt（n）的素數因子。