algorithm - a和b之间的数字除数的总和

假设有一个函数 g(x)= x 的除数。给定两个整数a和b，我们需要找到->

g(a)+ g(a + 1).... + g(b)。

我以为这步->

for every x from a to b

sum+=number of divisor of x(in sqrt(x) complexity)

但其给定的 1

所以在a和b之间进行迭代可能会花费我很多时间....例如->如果a = 1和b = 2 ^ 31-1。

有更好的方法吗？

最佳答案

这是完成这项工作的一些简单但相当有效的Python代码。

import math

def T(n):
    "Return sum_{i=1}^n d(i), where d(i) is the number of divisors of i."
    f = int(math.floor(math.sqrt(n)))
    return 2 * sum(n // x for x in range(1, f+1)) - f**2

def count_divisors(a, b):
    "Return sum_{i=a}^b d(i), where d(i) is the number of divisors of i."
    return T(b) - T(a-1)

说明:足以计算从1到b的总和，然后我们可以做两个单独的计算，然后减去以从a到b求和。找到从1到b的除数函数之和就等于从在线整数序列百科全书中计算sequence A006218。该序列等于floor(n / d)的总和，因为d的范围是从1到n的所有整数。

现在，可以将该序列视为双曲线xy=n下的整数值点的数量。我们可以使用x = y线周围的双曲线的对称性，并使用x <= sqrt(n)和使用y <= sqrt(n)计数整数点。最终重复计算点x和y都小于sqrt(n)的点，因此我们减去floor(sqrt(n))的平方以进行补偿。所有这些都在this paper的简介中进行了简要说明。

评论:

该算法具有运行时间O(sqrt(b))，并且空间要求恒定。可以节省时间来改善运行时间；请参阅上面提到的论文。

对于非常大的n，您需要一个合适的整数平方根，而不要使用floor(math.sqrt(n))，以避免浮点数不正确的问题。这与您正在查看的n类型无关。使用典型的IEEE 754浮点和正确取整的平方根运算，直到n超过2**52时，您才不会遇到麻烦。

如果a和b确实很接近，则可能会有更有效的解决方案。

关于algorithm - a和b之间的数字除数的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19381617/