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

Question

当用较大的整数（例如600851475143）替换x该get_large函数时，程序将停顿并且不返回值。但是，当x用较小的整数（例如20）替换时，它将返回结果。我怎样才能解决这个问题？factors = []  # create new empty listdef 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 factorsdef get_large(x):    calc(x)  # call the returned values in factors list    return calc(x)[-1]  # return the last factor in the listprint("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 factors

def 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):

    factors = []

    i = 2

    while i < x:

        while x % i == 0:

            x /= i

            factors += [i]

        i += 1

    return factors

def get_large(x):

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

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

结果，包括时间：

$ time python3 x.py

The largest factor is: 1471

real    0m0.065s

user    0m0.020s

sys 0m0.004s

Answer 3

import math

def get_large(x):

    for n in range(2, math.ceil(math.sqrt(x))):

        if x % n == 0:

            return x / n

    return 1

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

您的代码效率太低，因此要花大量时间才能永远运行。上面是一个更有效的版本。