algorithm - 有效地找到从 1 到 10^6 的所有数字的所有约数

Question

我需要找到 1 到 n(包括 1 和 n)之间所有数字的所有约数。其中 n 等于 10^6，我想将它们存储在向量中。

vector< vector<int> > divisors(1000000);
void abc()
{
    long int n=1,num;
    while(n<1000000)
    {
        num=n;
        int limit=sqrt(num);
        for(long int i=1;i<limit;i++)
        {
            if(num%i==0)
            {
                divisors[n].push_back(i);
                divisors[n].push_back(num/i);
            }
        }
        n++;
    }
}

这也花费了太多时间。我可以以任何方式优化它吗？

Answer 1

const int N = 1000000;
vector<vector<int>> divisors(N+1);

for (int i = 2; i <= N; i++) {
  for (j = i; j <= N; j += i) {
    divisors[j].push_back(i);
  }
}

运行时间为O(N*log(N))

直觉是上面的 N/2 个数字只运行一次。然后从剩余的数字中再次运行上半部分......

反过来说。如果将 N 从 10^6 增加到 10^7，那么您的操作数将达到 10^6 乘以 10 的数量(这是线性的)，但额外的是从 10^6 到 10^7 的数字最坏情况下每次运行次数不会超过 10 次。

操作次数为

sum (N/n for n from 1 to N)

这就变成了N * sum(1/n for n from 1 to N)，这是N*log(N)，可以使用以下积分来显示1/x 比 dx 从 1 到 N

我们可以看到算法是最优的，因为除数的数量有多少操作就有多少。结果的大小或除数总数与算法的复杂度相同。