python问题求解答

请问大家知道这是怎么回事吗？老是运行超时，应该怎么优化一下呢？

这个代码的瓶颈在于它的时间复杂度是指数级别的。在每次迭代中，你都从2开始遍历到n，所以总时间复杂度为O(n^2)。

要优化这个代码可以使用一些算法来减少遍历的次数，比如质因数分解。

def prime_factorization(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

# 使用示例
print(prime_factorization(n))

望采纳。

望采纳

你这种实现方式，循环的次数会累积，最后时间复杂度是指数级别的。

• 因为每次迭代，你都从2开始遍历到n，总时间复杂度为O(n^2)。
• 可以使用一些算法来减少遍历的次数，比如质因数分解。

def prime_factorization(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

# 使用示例
print(prime_factorization(n))

你这if，else写的纯粹多余，导致必须循环足够n次
i就根本不可能等于n

n=int(input())
i=2
while 1:
    if n%i==0:
        n//=i
        break
    i+=1