python-3.x 返回数字的最大因子非常慢

ippsafx7  于 2023-01-18  发布在  Python
关注(0)|答案(4)|浏览(132)

get_large函数中的x被替换为一个大整数,例如600851475143时,程序会停止并且不返回值。但是,当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)))
wr98u20j

wr98u20j1#

这是我的,注意factorscalc()的本地变量,所以我们不会一直追加到前面的列表。
还要注意,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
xfb7svmp

xfb7svmp2#

它可能没有坏,只是花了很长时间。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会让我们一无所获:)

b1zrtrql

b1zrtrql3#

如果数本身不是最大因子,那么为什么要循环到x,它可以循环到x/2。

tvz2xvvm

tvz2xvvm4#

[编辑]

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

你的代码效率太低了,所以要花很长时间来运行大量的数字。上面是一个更有效的版本。

相关问题