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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java-如何优化因子计数算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1065字，纯文字阅读大概需要2分钟。

内容图文

我被要求将除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;
}

是否有人有任何优化建议.

解决方法:

我在这篇文章的开头提出了最好的主意：

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

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

现在,您只需要执行一次测试(i * i)！= num O(max)次. (对于(int i = 2; i ** <** max; i)然后检查平方根).您确实说了很多数字,这样可以节省一些时间. 还有这是什么if(num / i< max){
                max = num / i;
            如果我没看错,那是多余的.在这个循环中,永远不会发生因数i大于num的平方根的情况.

最后,在空间允许的情况下,您可以使外部循环通过我将循环通过内部的数组.由于不需要重复i * i,因此可以节省一点点.这些只是您当前算法的微优化.

内容总结

以上是互联网集市为您收集整理的java-如何优化因子计数算法全部内容，希望文章能够帮你解决java-如何优化因子计数算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---