时间戳

首页 > 解决方案 > 数的因式分解优化

algorithm - 数的因式分解优化

问题描述

如何优化给定的这段代码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

标签： algorithmtimenumbersrefactoring

解决方案

所以你做了一些多算：

对于具有值 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 的答案，然后将答案数组硬编码到代码中。

推荐阅读