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写求1000内的所有完数，

好的，以下是Python代码实现：

# 求 1000 以内的完数
for i in range(2, 1001):
    factor_sum = 1
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            factor_sum += j
            # 注意判断 j 和 i/j 是否相等
            if j != i // j:
                factor_sum += i // j
    if factor_sum == i:
        print(i)

完数即为其所有因子（除数）之和等于它本身的正整数。上述代码首先从 2 开始遍历所有正整数，对于每个数，内循环遍历其所有可能因子，当找到一个因子时，将其加入因子和中，同时将其相对应的因子（即 i/j）也加入因子和中，最后判断因子和是否等于该数本身即可得到结果。在本例中，因子和计算的过程使用了平方数作为优化，可以降低时间复杂度。