假设要求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,运行将花费太多时间那么,如果b-a相对于a和b很小,而a和b很大(10^9或更大),那么可以进行哪种优化呢?
另外,也许我不能很好地解释这个问题。我真正需要找到的是,这个范围内有多少个数的除数等于一些x <= 100.
谢谢。

最佳答案

基本的答案是计算每个感兴趣的数的因子分解,然后用它来计算除数:如果因子分解是a^w*b^x*c^y*d^z,那么除数是(w+1)*(x+1)*(y+1)*(z+1)。
你可以用几种方法找到因式分解一种方法是通过审判庭;由于10^9的限制很小,审判庭工作时不会有太大的痛苦。另一种方法是通过筛分,使用埃拉托申斯的分段筛子来找到因子,然后通过除法计算它们的多重性。
你可以在my blog上找到试算除法的算法和代码,埃拉托森的分段筛,以及计算一个数的除数单击菜单栏上的练习,然后单击主题,然后选择素数。
编辑:我会这样做的。
第一步是筛选范围内所有数字的因子。用埃拉托舍内斯筛计算小于b的平方根的素数创建一个长度为b-a+1的数组,每个元素初始化为空列表。对于小于b的平方根的每个素数,计算第一个大于或等于a的数字k,这是素数的倍数,然后对于每个数组元素,从k-a开始,以p--k-a+p、k-a+2p、k-a+3p等间隔,将p添加到数组位置的列表中这给出了范围内所有数字的因子列表,但不是它们的多重性。
第二步是计算范围内所有数的除数数组的每个元素i都包含一个列表。如果列表为空,则数字为素数,数字a+i有两个除数。否则,使用列表中已知因子的试算除法来确定它们的重数,并使用这些重数来计算除数。
然后你用等于x的除数来计算范围内的那些。

07-24 17:41
查看更多