Python求整数所有因子，时间复杂度低

可以使用如下的代码实现求整数所有因子，时间复杂度为 O(sqrt(N))：

def get_factors(num):
    factors = []
    i = 1
    while i*i <= num:
        if num % i == 0:
            factors.append(i)
            if i != num // i:
                factors.append(num // i)
        i += 1
    return sorted(factors)

该代码使用一个 while 循环，从 1 到 sqrt(num) 遍历所有可能的因子，如果发现 num 可以整除 i，则将 i 和 num // i 两个因子加入 factors 中，如果 i 和 num // i 相等，则只将 i 加入 factors 中。最后将 factors 排序后返回即可。

相关问题

用Python写一个时间复杂度低的求完美数的算法，

当然，我会为您提供一个时间复杂度低的完美数算法。首先，让我们回顾一下什么是完美数：一个正整数等于它的因子（不包括自身）之和，则称该数为完美数。例如，6 是一个完美数，因为它的因子是 1，2，3，且 1+2+3=6。

下面是使用 Python 编写的时间复杂度低的完美数算法：

def perfect_number(n):
    i = 2
    sum = 1
    while i * i <= n:
        if n % i == 0:
            sum += i
            if i * i != n:
                sum += n // i
        i += 1
    if sum == n and n != 1:
        return True
    return False

这个算法的时间复杂度是 O(sqrt(n))，因为它只需要遍历 n 的平方根以下的数字来查找因子。

使用该算法，您可以轻松地检查给定数字是否为完美数，例如：

print(perfect_number(6))  # True
print(perfect_number(28))  # True
print(perfect_number(496))  # True
print(perfect_number(8128))  # True
print(perfect_number(27))  # False

希望这个算法对您有所帮助！

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