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

给定范围[1,200万]，对于此范围内的每个数字，我需要生成并将每个整数的除数的数量存储在数组中。有效计算范围内整数除数的总数

所以，如果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; 
     } 
    } 
}

来源

2012-02-06 praveen

首先你的公式是错误的。根据你的公式，12的除数总和应该是12，实际上是28.正确的公式是(p₁^a₁ - 1)*(p₂^a₂ - 1) * ... * (p_k^a_k - 1)/((p₁ - 1) * (p₂ - 1) * ... * (p_k - 1))。

也就是说，最简单的方法可能只是做一个筛子。人们可以通过偏移量来获得灵巧，但为了简单起见，只需制作一组2000,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到2百万的数组，列出每个数字的主要因子，从而提高效率。建立该阵列速度相当快，您可以采取任何数量并将其分解得多，速度比您尝试分区时快得多。

来源

2012-02-07 07:01:55 btilly

感谢您的回答。我很抱歉我提出了错误的问题。我实际上需要每个整数除以200万以下的除数。 – praveen 2012-02-07 10:55:18

@praveen然后只是因素[j] ++;'而不是因素[j] + = i;'。 – btilly 2012-02-07 14:24:27

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

回答

相关问题