python - 返回一个包含素数的数组，其乘积为 x

Question

我迷路了。我的函数在某些情况下有效，但在某些情况下无效。例如，提供数字 110019 它应该返回一个数组 [13,13,3,7,31] 而它不是...

def primeFactorization(x):
    i=2
    array=[]
    for i in range(i,x+1):
        if x % i == 0:
            j=2
            for j in range(j,x+1):
                if i % j == 0:
                i=j
            array.append(i)
            product_value=1
            for j in array:
                product_value=j*product_value
                if product_value == x:
                    array.sort()
                    return array
    return []

Answer 1

一些问题:

• j 上的循环毫无用处。它里面的 if 唯一一次为真，是当 i == j 时，因为在那之后 j 只会增加。此外，分配 i = j 没有任何改变，因为当发生这种情况时它们已经相等

• 您的代码永远不能两次附加相同的值，但这可能是必要的。

• 每次都从头开始计算乘积是浪费时间。您应该在附加新因素时逐步执行此操作。最好从相反的方向开始工作，并根据找到的每个因素划分 x。这样你就可以避免找到非主要因素。

• 对列表进行排序没有用，因为 i 在您的代码中增加，所以当您将 i 附加到列表时，列表将始终保留排序。

这是它的工作原理:

def primeFactorization(x):
    lst = []
    i = 2
    while x > 1:
        while x % i == 0:
            lst.append(i)
            x //= i
        i += 1
    return lst

print (primeFactorization(110019))