分解质因数python函数

在Python中，分解质因数是一个常见的数学操作，通常用于简化大整数的表达。你可以通过循环和除法来实现一个简单的质因数分解函数。下面是一个示例函数：

def prime_factors(n):
    factors = []
    # 循环检查每个数是否能整除n
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            factors.append(i)
            n //= i
            # 如果n变成1，说明已经找到了所有质因子
            if n == 1:
                break

    # 如果n大于1，剩下的可能是最后一个质因子（如果n本身是质数）
    if n > 1:
        factors.append(n)

    return factors

# 使用示例
print(prime_factors(60))  # 输出：[2, 2, 3, 5]

这个函数首先从2开始尝试，找到并记录可以整除n的数，然后更新n。当n不再能被当前数整除时，继续找下一个质数。最后，如果n还有剩余并且大于1，那么n本身也是一个质数。

相关问题

分解质因数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`数组的更新速度。

分解质因数Python

分解质因数是指将一个正整数分解成若干个质数的乘积的过程。下面是一个用Python实现分解质因数的示例代码：

def prime_factors(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

num = int(input("请输入一个正整数："))
result = prime_factors(num)
print(f"{num}的质因数为：{result}")

这段代码定义了一个名为`prime_factors`的函数，接受一个正整数`n`作为参数，并返回一个列表，包含`n`的所有质因数。在主程序中，用户输入一个正整数，然后调用`prime_factors`函数进行分解质因数，并将结果打印输出。