python经典百题之分解质因数_分解质因数python

质因数是指一个正整数可以分解成若干个质数的乘积，其中每个质数都是这个正整数的因数。例如，数字 12 可以分解成 2 × 2 × 3 的形式，其中 2 和 3 都是质数，因此它们是数字 12 的质因数。

算法一：暴力枚举法

思路：从2到n-1依次判断n是否能够被整除，如果能够被整除，则说明存在一个质因数，将其保存下来，并将n除以该质因数，然后继续对n进行同样的操作。重复上述步骤，直到n变为1，最终得到所有的质因数。

代码实现：

def prime_factor(num):
    factors = []
    i = 2
    while i <= num:
        if num % i == 0:
            factors.append(i)
            num = num // i
            i = 2
        else:
            i += 1
    return factors

优劣分析：

暴力枚举法的时间复杂度为O(n)，当n较小时，该算法具有一定的优势。然而当n较大时，时间复杂度较高，算法效率较低。

算法二：分解质因数法

思路：对于一个正整数n，如果其存在质因数p，则n可以表示为n=p*q，其中q为除p外的其他质因数的乘积。因此，我们可以先判断2是否是n的质因数，如果是，则将其保存下来，并将n除以2，继续进行同样的操作，直到n为奇数，然后从3开始，依次判断所有的奇数是否是n的质因数。由于n除以每个质因数后都会变得更小，因此当n不是质数时，分解质因数后得到的所有质因数必然都小于或等于n的平方根。

代码实现：

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

优劣分析：

分解质因数法的时间复杂度为O(sqrt(n))，相对于暴力枚举法，其时间复杂度更低，因此在处理较大的正整数时，该算法会更加高效。

算法三：试除法

思路：对于一个正整数n，如果其存在质因数p，则n可以表示为n=p*q，其中q为除p外的其他质因数的乘积。我们可以依次从2到n-1进行试除，如果发现某个数i能够被n整除，则说明i是n的一个质因数，将其保存下来，并将n除以i，然后继续进行同样的操作。由于n中可能存在大于n的平方根的质因数，因此，我们只需要试除到n的平方根即可。

代码实现：

import math
def prime_factor(num):
    factors = []
    i = 2
    while i <= math.sqrt(num):
        if num % i == 0:
            factors.append(i)
            num = num // i
        else:
            i += 1
    if num > 1:
        factors.append(num)
    return factors

优劣分析：

试除法的时间复杂度为O(sqrt(n))，与分解质因数法的时间复杂度相同。然而，在实际运行中，试除法的效率并不如分解质因数法，因为试除法需要进行大量的除法运算，而分解质因数法只需要进行少数的除法运算，因此试除法的效率较低。

综合上述三种算法，分解质因数法是效率最高的算法，而暴力枚举法虽然简单，但是其时间复杂度高，只适用于处理小数据的情况。