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

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）的素数因子。