设函数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<2^31-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求除数函数的和等于从整数序列的在线百科全书计算序列A006218。该序列等价于floor(n / d)的和，因为d在从1到n的所有整数上。
现在这个序列可以看作是双曲面xy=n下的整数值点的数量。我们可以利用双曲线围绕x = y线的对称性，计算出x <= sqrt(n)和y <= sqrt(n)的整数点。这最终会使x和y都小于sqrt(n)的点加倍计数，因此我们减去floor(sqrt(n))的平方来进行补偿。所有这些都在本文的引言中作了简要的解释。
备注：
该算法具有运行时间
O(sqrt(b))和恒定的空间要求。运行时间的改进是以牺牲空间为代价的；参见上文提到的论文。对于真正大的
n，您需要一个合适的整数平方根，而不是使用floor(math.sqrt(n))，以避免浮点不准确的问题。这不是你所看到的那种n的问题。使用典型的IEEE 754浮点和正确取整的平方根运算，在n超过2**52之前，你不会遇到麻烦。如果
a和b真的接近，则可能存在更有效的解决方案。
因为所需的结果是一个范围内所有数字的除数总数，所以不需要计算该范围内单个数字的除子；相反，计算1是除数、2是除数等的次数。这是O(b(计算。
即将b-(a-1)、b/2 - (a-1)/2、b/3 - (a-1)/3等相加
在下面显示的python代码中(使用python运算符//进行带截断的整数除法(，使用for循环对2到大约b/2的除数进行计数。注意，小于b但大于max(a, b/2)的除数每个出现一次，并且不需要在循环中计数。代码使用表达式b-max(a,(b+1)//2+1)+1对它们进行计数。输出显示在程序之后。
当要处理k不同的a,b集合时，可以计算时间O(k+bₘₐₓ(中的所有答案，其中bₘₐₓ是b的最大值。
Python代码：
def countdivisors(a,b):
mid = (b+1)//2+1
count = b-a+1 +b-max(a,mid)+1 # Count for d=1 & d=n
for d in xrange(2,mid):
count += b//d - (a-1)//d
return count
# Test it:
a=7
for b in range(a,a+16):
print '{:3} {:3} : {:5}'.format(a, b, countdivisors(a,b))
输出：
7 7 : 2
7 8 : 6
7 9 : 9
7 10 : 13
7 11 : 15
7 12 : 21
7 13 : 23
7 14 : 27
7 15 : 31
7 16 : 36
7 17 : 38
7 18 : 44
7 19 : 46
7 20 : 52
7 21 : 56
7 22 : 60
您可以筛选除数，然后对计数求和：
function divCount(a,b)
num := makeArray(1..b, 0)
for i from 1 to b
for j from i to b step i
num[j] := num[j] + 1
sum := 0
for i from a to b
sum := sum + num[i]
return sum
这类似于Eratosthenes筛，但它没有标出复合物，而是对每个数字的每个除数进行计数，包括素数和复合物。如果b太大，可以分段进行筛选。
另一个基于筛选的答案，但时间复杂度比其他答案更好。这个也很容易处理分割，因为它每次只筛选数字{a...b}。该函数返回一个int[]，其中从a到b的每个数都有除数。只要把它们加起来就可以得到最终的答案。
如果您的输入较大，您可以将其拆分，并将每个返回段的总和相加。
Java：
public static int[] getDivisorCount(int a, int b){
int[] sieve = new int[b - a + 1];
double max = Math.ceil(Math.sqrt(b));
for(int i = 1; i <= max; i++){
int j = (a / i) * i;
if(j < a)
j += i;
for( ; j <= b; j += i){
double root = Math.sqrt(j);
if(i < root){
sieve[j - a] += 2;
}else if(i == root){
sieve[j - a]++;
}
}
}
return sieve;
}
外循环运行sqrt(b)次。内部循环运行类似log(b-a)的次数，所以除非我错了，否则最终的复杂性应该是类似O(sqrt(b) * log(b))的，因为最坏的情况是a=1。请随时纠正我的错误。
如果您正在处理大量输入，并且有多余的空间，那么您可能需要考虑预填充sqrt表，以使其脱离内部循环。它会加快速度，如果你有多余的内存，就没有真正的缺点。
为了快速测试，这里有一个ideone.com的例子。
编辑：如果你正在寻找一个筛子，这很好。然而，我必须说，jwpat7的答案是1(更快，2(恒定空间，3(更优雅(IMO(。基本上没有理由使用筛子，除非你对它的机制感兴趣。
我们可以调整此算法：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes在所有倍数上加1，而不是将它们标记为"非素数">
它将是o(n.ln(n((，其中a=1并且b=n(我认为(
1到n:的算法
g: array of n elements
for i starting with 2 to n
if g[i]== 0
for each multiple of i <n
g[i] += 1