1

假设要找到 1 到 N 之间所有数字的除数，我们使用：

for (i = 1; i < N; ++i) 
    for (j = i; j < N; j += i) 
        factors[j]++;

如果范围是[a,b]这样的，我们应该怎么做1 < a,b < 10^9 and b-a < 10,000?
如果我们将上面的代码修改为：

for (i = 1; i < b; ++i)
    for (j = i; j < b; j += i)
        factors[j]++;

如果b = 10^9. 那么，假设 ba 相对于 a 和 b 较小，而 a 和 b 较大（10^9 或更大），可以进行什么样的优化？

PS。也许我无法很好地解释这个问题。我真正需要找到的是该范围内有多少个数的除数等于一些x <= 100.

谢谢。

4

2 回答 2

2

基本答案是计算每个感兴趣数字的分解，然后用它来计算除数：如果分解是 a^w * b^x * c^y * d^z 那么除数是 ( w+1) * (x+1) * (y+1) * (z+1)。

您可以通过多种方式找到分解。一种方式是通过试划分；由于 10^9 的限制很小，所以试用除法将不会太痛苦。另一种方法是通过筛选，使用分段的 Eratosthenes 筛子来查找因子，然后通过除法计算它们的多重性。

您可以在我的博客上找到用于试验除法、Eratosthenes 分段筛以及计算数字除数的算法和代码。单击菜单栏上的练习，然后单击主题，然后选择质数。

编辑：我会这样做。

第一步是筛选范围内所有数字的因子。使用埃拉托色尼筛法计算小于b平方根的素数。创建一个长度为b - a + 1的数组，其中每个元素都初始化为一个空列表。对于小于b的平方根的每个素数，计算大于或等于a的第一个数k，它是素数的倍数，然后对于从k - a开始且间隔为p - k - a +的每个数组元素, k - a + 2p、k - a + 3 p等等——将p添加到数组位置的列表中。这为您提供了该范围内所有数字的因子列表，但不是它们的多重性。

第二步是计算范围内所有数字的除数。数组的每个元素i都包含一个列表。如果列表为空，则数字是素数，并且数字a + i有两个除数。否则，使用列表中已知因子的试除法来确定它们的多重性，并使用这些多重性来计算除数的数量。

然后，您只需计算除数等于x的范围内的那些。

于 2012-12-19T03:13:53.997 回答
0

对于任何数字 n，例如： 1 < a <= n <= b < 10^9 ，一个非常简单的算法将为您提供 n 的素数分解（您不需要比 sqrt(n) 更进一步）。然后一个你有它，一个公式会给你不同除数的数量。

由于您必须处理的 n 数量非常小，这应该可行。

于 2012-12-19T03:03:47.663 回答