有效计算范围内整数的除数总数

Question

给定范围 [1, 2 百万]，对于这个范围内的每个数字，我需要生成 并将每个整数的约数个数存储在数组中。

因此，如果 x=p1^(a1)*p2^a2*p3^a3，其中 p1、p2、p3 是素数， x 的约数总数由 (p1+1)(p2+1)(p3+1) 给出。我生成了所有 2000 以下的素数，对于该范围内的每个整数，我进行了试除法 得到每个质因数的幂，然后用上面的公式计算 除数的数量并存储在数组中。 但是，这样做非常慢，大约需要 5 秒才能生成除数的数量 对于给定范围内的所有数字。

我们可以用其他有效的方式求和吗？可能不需要分解每个 数字？

下面是我现在使用的代码。

typedef unsigned long long ull;
void countDivisors(){
    ull PF_idx=0, PF=0, ans=1, N=0, power;
    for(ull i=2; i<MAX; ++i){
        if (i<SIEVE_SIZE and isPrime[i]) factors[i]=2;
        else{
        PF_idx=0;
        PF=primes[PF_idx];
        ans=1;
        N=i;
        while(N!=1 and (PF*PF<=N)){
            power = 0;
            while(N%PF==0){ N/=PF; ++power;}
            ans*=(power+1);
            PF = primes[++PF_idx];
        }
        if (N!=1) ans*=2;
        factors[i] = ans;
        }
    }
}

Answer 1

首先你的公式是错误的。根据你的公式，12的约数之和应该是12。实际上是28。正确的公式是 (p1a1 - 1)*(p2a2 - 1) * ... * (pkak - 1)/( (p1 - 1) * (p 2 - 1) * ... * (pk - 1) )。

也就是说，最简单的方法可能就是进行筛子。人们可以巧妙地利用偏移量，但为了简单起见，只需创建一个包含 2,000,001 个整数（从 0 到 200 万）的数组。将其初始化为 0。然后：

for (ull i = 1; i < MAX; ++i) {
    for (ull j = i; j < MAX; j += i) {
        factors[j] += i;
    }
}

这可能感觉效率低下，但也没有那么糟糕。 N 之前的数字所需的总功为 N + N/2 + N/3 + ... + N/N = O(N log(N)) 这比试除法要小几个数量级。而且运算都是加法和比较，对于整数来说速度很快。

如果您想继续使用原来的想法和公式，您可以使用改进的埃拉托斯特尼筛创建一个 1 到 200 万的数组，列出每个数字的素因数，从而提高效率。构建该数组相当快，您可以获取任何数字并对其进行因式分解，这比使用试除法要快得多。