方法I 从1到n枚举，判断是否可以整除

时间复杂度 O(n)

Python代码：

def countDivisors(num):
    return sum(num % i == 0 for i in range(1, num + 1))

方法II 从1到sqrt(n)枚举，判断是否可以整除

时间复杂度 O( sqrt(n) )

Python代码：

def countDivisors(num):
    cnt = 0
    sqrt = int(num ** 0.5)
    for x in range(1, sqrt + 1):
        if num % x == 0:
            cnt += 1
    return cnt * 2 - (sqrt ** 2 == num)

方法III 分解质因子，求幂的乘积

时间复杂度 O( sqrt(n) )

Python代码：

def countDivisors(num):
    ans = 1
    x = 2
    while x * x <= num:
        cnt = 1
        while num % x == 0:
            cnt += 1
            num /= x
        ans *= cnt
        x += 1
    return ans * (1 + (num > 1))

 

本文链接：http://bookshadow.com/weblog/2016/11/27/python-divisor-count/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码