返回数字的最大因数非常慢

Question

当用较大的整数（例如600851475143）替换x该get_large函数时，程序将停顿并且不返回值。但是，当x用较小的整数（例如20）替换时，它将返回结果。我怎样才能解决这个问题？

factors = []  # create new empty list

def calc(x):

    for n in range(1, x):

        if x % n == 0:

            factors.append(n)  # if x is divisible by n append to factor list

    return factors

def get_large(x):

    calc(x)  # call the returned values in factors list

    return calc(x)[-1]  # return the last factor in the list

print("The largest factor is: " + str(get_large(600851475143)))

Answer 1

它可能没有坏，只是花了很长时间。Python以运行大for循环时速度较慢而著称。我建议类似以下内容：def calc(x):    n = 2    factors = []    while x != n:        if x % n == 0:            factors.append(n) #if x is divisible by n append to factor list            x = x / n #this will safely and quickly reduce your big number            n = 2 #then start back at the smallest potential factor        else:            n = n + 1    return factors #This will return a list of all prime factorsdef get_large(x):    bigFactor = x / calc(x)[0]    #The largest factor is just the original    #number divided by its smallest prime factor    return bigFactor我使用2作为最小的潜在因数，因为使用1会使我们无处可去:)

Answer 2

这是我的。请注意，这factors是本地的，calc()因此我们不会不断将其附加到上一个列表中。另请注意，get_large()只需调用calc()一次即可。没有理由两次调用它。最后，我将您的算法替换为calc()应该快得多的算法。def calc(x):&nbsp; &nbsp; factors = []&nbsp; &nbsp; i = 2&nbsp; &nbsp; while i < x:&nbsp; &nbsp; &nbsp; &nbsp; while x % i == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x /= i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; factors += [i]&nbsp; &nbsp; &nbsp; &nbsp; i += 1&nbsp; &nbsp; return factorsdef get_large(x):&nbsp; &nbsp; return calc(x)[-1] #return the last factor in the listprint ("The largest factor is: " +str(get_large(600851475143)))结果，包括时间：$ time python3 x.pyThe largest factor is: 1471real&nbsp; &nbsp; 0m0.065suser&nbsp; &nbsp; 0m0.020ssys 0m0.004s

Answer 3

import mathdef get_large(x):&nbsp; &nbsp; for n in range(2, math.ceil(math.sqrt(x))):&nbsp; &nbsp; &nbsp; &nbsp; if x % n == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return x / n&nbsp; &nbsp; return 1print ("The largest factor is: " +str(get_large(600851475143)))您的代码效率太低，因此要花大量时间才能永远运行。上面是一个更有效的版本。