java - 如何优化因子计数算法

Question

我被要求对除 1 以外的因数和数组中每个数字的数字本身求和。问题是它必须能够处理具有非常大数字的非常大的数组，而我当前的实现对于大小为 100,000,000 的数组需要很长时间。我计算每个数字因子的代码是

static long countFactors(long num){
    long count=0;
    long max =(long) Math.floor(Math.sqrt(num));
    for(int i=2; i<=max;i++){
        if(num%i==0&&(i*i)!=num){
            // count i and n/i as a factor
            count+=2;
            if(num/i<max){
                max=num/i;
            }
        }            
        else if(num%i==0){
            // just add one factor since it is the numbers root.
            count+=1;

        }
    }

    return count;
}

有没有人有什么优化建议

Answer 1

我把最好的想法放在这篇文章的开头:

可被 n 整除的数字可以被 n 的所有因数整除.

也许这是降低时间复杂度的关键。现在剩下的:

现在您执行测试 (i*i)!=num O(max) 次，只需要完成一次。 (for(int i=2; i**<**max;i++) 然后检查平方根)。你确实说了很大的数字，所以这可以节省一点。

还有这是什么？ if(num/i<max){ max=num/i; }如果我没看错的话，这是多余的。从来没有发生过一个因素i在这个循环中大于 num 的平方根.

最后，如果空间允许，您可以使外部循环遍历 i把循环穿过数组放在里面。由于不需要重复 i*i，这将节省一点点.这些只是对您当前算法的微优化。