algorithm - 数字的分解优化

Question

给定 N<=1000 如何优化此代码？我尝试对每个数字进行因式分解，但这很耗时:

cnt = 0 ;
 for int i=1 to N
    for int j=1 to N
        for int k=1 to N
        if(i*j)%k==0 
         cnt = cnt + 1

Answer 1

所以你多算了一些:

对于具有值 x = i * j 的每一对 i,j 你运行一个循环 k 次，但是有很多对 i*j 给出相同的值

并且您使用模数 N^3 次，记住模数很昂贵。

优化:

1. 不是对所有 i * j 对进行过度计数，而是将它们存储在哈希表/数组中并计算它们的频率

2. 当一些数字 x 除以 k 得到模数 0 时，而不是使用模数来使用一些数学进行优化？仅当 x 是 k 的倍数时，所以只需以 k 为增量循环从 0 到 n*n 的频率

示例代码(C++):

vector<int>freq(n*n+1); //that's just array of n*n+1 zeroes

for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
    freq[i*j]++;

int cnt = 0;
for(int k=1; k<=n; k++)
    for(int j=0; j<=n*n; j+=k) //note these loops look like n^3 at first glance yet it's something like n log (n*n) (check harmonic number if you're curious why)
    cnt+=freq[j];

更多优化:

嗯，1000 不是很多，即使每个数字占用 64 位，它也像 ~8KB 内存。因此，您可以选择在某个数组中生成所有答案，例如 answer[n] 存储某个 n 的答案，然后将答案数组硬编码到代码中。