主页 / 问题 / 1248005
Accepted
Oleg Chaika
Asked:2022-02-24 17:06:34 +0000 UTC2022-02-24 17:06:34 +0000 UTC

优化数除数的搜索功能

  • 772

任务是找到严格大于 b 的数除以数 n。我写了一个简单的函数：

def get_ls(n, b):
    i = b+1
    k = 0
    while i <= n:
        if (n%i==0):
            k += 1
            i += 1
        else:
            i += 1
    return k

但是，当然，它的工作非常缓慢。您能建议加快速度的方法吗？提前致谢。

python

1 个回答

  1. Best Answer

    理论上你应该这样做：

    import math

def get_ls(n, b):
    count = 0

    for i in range(1, int(math.sqrt(n + 1)) + 1):
        if n % i == 0:
            count += 1 if i > b else 0
            count += 1 if n // i > b else 0

    return count


print(get_ls(123456789098765, 4321)) # res = 12, работает около 2-3 сек

    大意 -

    1. 我们不需要考虑从b到的所有数字n

    2. 我们只需要考虑从1到 的数字sqrt(n)

    3. 有必要考虑 2 个乘数 -i并n // i查看其中哪些大于 b

    因此，任务的复杂性不是O(n)，而是O(sqrt(n))

    附言

    膝盖上写了代码，理论上可以再优化一点，但主要是实现了速度的提升

    • 1

相关问题