Python - 将数字的因子按排序顺序放入数组

Question

我已经编写了这个算法来找到给定数字的所有因子并将它们放入列表中:

def find_all_factors(n):
    factors = []
    for i in range(1, floor(sqrt(n))+1):
        if n % i == 0:
            factors.append(i)
            cofactor = n // i
            if i != cofactor: factors.append(cofactor)
    return factors

在列表中，辅因子将彼此相邻放置，但我希望它们按排序顺序出现。上述算法的输出示例:对于 n = 36，它输出 [1, 36, 2, 18, 3, 12, 4, 9, 6]。我这样做是为了练习，我想知道让它们按排序顺序排列的最有效方法是什么，有什么想法吗？

您可以在下面看到我的解决方案之一。它有效，但我不认为它是最佳的。

def find_all_factors(n):
    lower_factors = []
    higher_factors = []
    for i in range(1, floor(sqrt(n))+1):
        if n % i == 0:
            lower_factors.append(i)
            cofactor = n // i
            if i != cofactor: higher_factors.append(cofactor)
    return lower_factors + [higher_factors[-i] for i in range(1, len(higher_factors)+1)]  #Reverses higher_factors.

Answer 1

只需简单地返回排序后的列表:

return sorted(factors)

如果您不喜欢使用 sorted 函数，只需将循环范围更改为 (1,n+1) 即可:

def find_all_factors(n):
    factors = []
    for i in range(1, n+1):
        if n % i == 0:
            factors.append(i)
    return factors

find_all_factors(12) # [1, 2, 3, 4, 6, 12]

另一种方法是使用bisect(最有效的方法):

import bisect
def find_all_factors(n):
    factors = []
    for i in range(1, math.floor(math.sqrt(n))+1):
        if n % i == 0:
            bisect.insort(factors,i)
            cofactor = n // i
            if i != cofactor: bisect.insort(factors, cofactor)
    return factors

find_all_factors(12) # [1, 2, 3, 4, 6, 12]

在此模块中插入是 O(n) 而搜索是 O(log(n))