如何使用Python找到一个数的因数？

在数学中，因数是指在一定条件下可以整除某个数的数，例如2是4的因数，因为4除以2得2，也就是说，4可以被2整除。在程序开发中，我们经常会需要找到一个数的因数来进行计算，那么如何使用Python来找到一个数的因数呢？

常见方法

方法一：暴力求解

首先，我们可以使用最简单直接的方法——暴力求解来找出一个数的因数。具体实现过程为，从2开始遍历到该数的平方根，依次检查这个数是否能够被该数整除，如果是，那么就是该数的一个因数。通过这种方法，我们可以找到所有的因数。

示例代码：

def find_divisor1(num):
    """
    暴力求解找到所有的因数
    """
    res = set()  # 用集合保存因数，去除重复
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            res.add(i)
            res.add(num // i)
    res.add(1)
    res.add(num)
    return res

该方法的时间复杂度为 $O(\sqrt{n})$ ，空间复杂度为 $O(\sqrt{n})$ ，虽然找到了所有的因数，但是计算量很大，时间上不太优化。

方法二：改进暴力求解

针对方法一的问题，我们可以进行优化。因为一个数的因数是成对出现的，例如6的因数是1,2,3,6，其中1和6，2和3是成对出现的因数，因此我们只需要检查从2到这个数的开方，判断是否存在一个因数即可。

示例代码：

def find_divisor2(num):
    """
    改进暴力求解，从2到sqrt(num)找一个因数即可
    """
    res = set()  # 用集合保存因数，去除重复
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            res.add(i)
            res.add(num // i)
    if len(res) == 0:
        return {1, num}
    res.add(1)
    res.add(num)
    return res

该方法的时间复杂度为 $O(\sqrt{n})$ ，空间复杂度为 $O(\sqrt{n})$ ，相比于方法一缩短了运行时间，但是依旧不够优秀。

方法三：分解质因数

在数学中，我们知道，任何一个不是质数的数，都可以分解成多个质数的乘积。通过质因数分解这样的方法，我们可以非常快速地找到一个数的所有因数，适用于待分解的数较大的情况。

示例代码：

def find_divisor3(num):
    """
    分解质因数找到所有的因数
    """
    factors = []
    i = 2
    while i * i <= num:
        if num % i:
            i += 1
        else:
            num //= i
            factors.append(i)
    if num > 1:
        factors.append(num)
    res = set()
    for i in range(len(factors)):
        curr = factors[i]
        count = curr
        while curr <= num:
            if num % curr != 0:
                break
            res.add(count)
            count *= curr
            curr *= factors[i]
    if len(res) == 0:
        return {1, num}
    res.add(1)
    res.add(num)
    return res

该方法的时间复杂度为 $O(\log n)$ ，空间复杂度为 $O(\sqrt{n})$ ，但是因为分解质因数具有一定复杂度，适用于待分解的数较大的情况，小数的分解不太划算。