1

给定范围 [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;
        }
    }
}
4

1 回答 1

3

首先你的公式是错误的。根据你的公式，12的除数之和应该是12。实际上是28。正确的公式是。(p1a1 - 1)*(p2a2 - 1) * ... * (pkak - 1)/( (p1 - 1) * (p2 - 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))比试除法要小几个数量级。并且操作都是加法和比较，对于整数来说速度很快。

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

于 2012-02-07T07:01:55.023 回答