假设存在一个函数 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。
有更好的方法吗？
5个回答
4
这里有一些简单但相当有效的Python代码，可以完成任务。
解释：只需要能够计算从
现在，可以将该序列视为双曲线xy=n下整数值点的数量。我们可以利用双曲线关于x=y对称的性质，计算x<=sqrt(n)和y<=sqrt(n)的整数点。这最终会重复计算x和y都小于sqrt(n)的点，因此我们减去floor(sqrt(n))的平方以进行补偿。所有这些都在this paper的介绍中（简要）解释了。
备注：
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。该序列等同于在所有整数d从1到n范围内变化时的floor(n / d)的总和。现在，可以将该序列视为双曲线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很接近，则可能有更有效的解决方案。
- Mark Dickinson
1
非常优雅的答案，其中包含一些很好的技巧，这些技巧被很好地解释并且对于从未听说过除数和函数（
T，A006218）的人来说也是完全可理解的。此外，代码简洁高效。干得好！ - Bolo1
由于期望的结果是范围内所有数字的因子总数，因此无需计算范围内每个数字的因子；相反，计算1是因子的次数、2是因子的次数等等。这是O(b)的计算。
也就是说，将b-(a-1)、b/2 - (a-1)/2、b/3 - (a-1)/3等加起来。
在下面展示的Python代码中（使用Python运算符//进行整数除法并截断），从2到约b/2的因子使用for循环进行计数。请注意，小于b但大于max(a, b/2)的因子每个出现一次，无需在循环中计数。代码使用表达式b-max(a,(b+1)//2+1)+1进行计数。程序输出如下。
当需要处理 k 个不同的 a、b 集时，可以在 O(k+bₘₐₓ) 的时间内计算出所有答案，其中 bₘₐₓ 是 b 的最大值。
Python 代码:
也就是说，将b-(a-1)、b/2 - (a-1)/2、b/3 - (a-1)/3等加起来。
在下面展示的Python代码中（使用Python运算符//进行整数除法并截断），从2到约b/2的因子使用for循环进行计数。请注意，小于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
- James Waldby - jwpat7
0
你可以筛选出每个数的因子数量，然后将它们相加：
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
这类似于埃拉托斯特尼筛法，但不是标记合数，而是对每个数字计算每个除数，包括质数和合数。如果b太大，您可以分段进行筛选。
- user448810
3
为了节省时间，您可以将内部循环限制在sqrt(b)处，并添加2。如果它恰好等于平方根，则只需添加1。 - Geobits
@Geobits 我认为你做不到。我们正在创建一个筛子，而不是计算一个数字的所有除数。 - Bernhard Barker
0
另一种基于筛法的解决方案，但时间复杂度比其他方案更好。由于每次运行只筛选范围为
{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的答案更快，常数空间，而且更优雅（在我看来）。除非您对其机制感兴趣，否则基本上没有使用筛法的理由。
- Geobits
0
我们可以通过将所有倍数加1而不是标记为“非质数”来适应这个算法：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。
如果a=1且b=n，那么时间复杂度将是o(n.ln(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
- pdem
2
在筛法中，我们跳过一些合数，比如12，但它们可能是a和b之间某些数字的除数，我们应该多次计算它们。 - Saeed Amiri
是的，我没有看到那个。如果在循环i的每个倍数之前测试g[i]==0，它将起作用。只有当i是质数时，我们才会添加1。 - pdem
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
a和b对，还是只有一个？ - Bernhard Barker