【Leetcode刷题Python】改进的算法，高效求一个数的因子

1 思路

不用全部遍历，只遍历1到根号(n)的范围即可。 当i是可以整除的，用n/i得到的是相对另一个因子。 时间复杂度 O ( n 1 / 2 ) O(n^{1/2}) O(n1/2)

2 实现

import math
def low_fac(n):
    ans = []
    for i in range(1,int(math.sqrt(n))):
        
        if n%i==0:
            if i*i>n:
                ans.append(i)
            t = int(n/i)
            if t!=i and t*t>n:
                ans.append(t)
    return ans