分解质因数python函数，时间复杂度最低

在Python中，分解质因数通常会使用循环和除法操作来找到一个给定整数的所有质因子。下面是一个简单的函数示例，采用埃拉托斯特尼筛法优化，时间复杂度相对较低：

def prime_factors(n):
    factors = []
    # 将所有小于等于n的数标记为非质数（除了2）
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    
    # 使用埃拉托斯特尼筛法找出所有的质数
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # 将p的倍数标记为非质数
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1

    # 找到n的质因子并添加到列表中
    for p in range(2, n + 1):
        if is_prime[p] and n % p == 0:
            factors.append(p)
            n //= p
            # 如果n已经被完全除尽，跳出循环
            if n == 1:
                break

    return factors

# 示例
print(prime_factors(48))  # 输出：[2, 2, 2, 2, 3]

这个函数的时间复杂度大致是O(sqrt(n))，因为我们在筛选的过程中只需要检查到n的平方根。不过实际运行效率还取决于`is_prime`数组的更新速度。