Java遍历完数的一些思考

题目:打印出1~10000以内所有的完数

1.分析1

• 如果一个数恰好等于它的因子之和，则称该数为“完全数”。引用百度百科-完全数,如6=1＋2＋3
• 不包括数本身的所有的因子之和等于这个数，所以1不符合要求；
• 遍历所有2~10000的数，并且嵌套遍历0到该数范围内的所有预备因子，如果该数模预备因子等于0，则该预备因子为该数的因子，定义一个计数器，将所有因子累加，如果累加结果等于该数本身，即这个数为完数；
• 为了便于比较运算效率，引入System.currentTimeMillis()方法记录遍历前后的系统当前毫秒值；

2.代码:

public class PerfectNumberDemo {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        for (int num = 2; num <= 10000 ; num ++ ) {
            int sum = 0;
            for (int divisor = 1 ; divisor < num ; divisor ++) {
                if (num % divisor == 0 ) {
                    sum = divisor + sum;
                }
            }
            if (sum == num) {
                System.out.println(num);
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("遍历全部完数所使用的时间: " + (end - start) + " 毫秒");
    }
}

• 运行结果:
  普通方法

3.一点思考

• 判断10000这个数是否是完数需要遍历预备因子9999次，判断9999这个数是否是完全数需要遍历预备因子9998次，以此类推，根据等差数列求和公式需要遍历9998*(9999 + 2) / 2 = 49,994,999次，显然效率很低，需要进一步优化；
• 经过分析，完数的最大因子不会超过他本身的一半，所以可以把divisor < num改成divisor <= num / 2；
• 继续分析，如果数num的第2因子divisor2，则(num / divisor2)也一定是num的因子，则(num / divisor2)到num之间一定不会有因子出现，下一步预备因子遍历范围缩小到divisor2 ~ (num / divisor2)；
• 继续，如果数num的第3个因子divisor3，则(num / divisor3)也一定是num的因子，则(nmu / divisor3)到(num / divisor2)之间一定不会有因子出现，下一步预备因子遍历范围缩小到divisor3 ~ (num / divisor3)，以此类推即可；
• 将所有因子累加到计数器sum中，然后比较sum - num == num 即可，但是有个例外；
• 例如num=16，第3个因子divisor3是4，则(num / divisor3)还是4，因子4不能重复计入计数器，所以需要使用if ··· else if ···语句判断两种情况，分别累加因子；

4.代码优化

public class PerfectNumberTest {
    public static void main(String[] args) {
        int count = 0;//定义一个计数器
        System.out.println("1~10000范围内的所有完数如下:");
        long start = System.currentTimeMillis();
        for (int num = 2; num <= 10000 ; num ++ ) {
            int sum = 0;//定义一个因子求和公式
            for (int divisor = 1 ; divisor <= num / divisor ; divisor ++) {
                if (num % divisor == 0 && divisor != num / divisor) {//若num开根号结果不是他的因子
                    sum = divisor + (num / divisor) + sum;//则num/divisor也一定是他的因子
                } else if (num % divisor == 0 && divisor == num / divisor) {//若num开根号的结果是他的因子
                    sum = divisor + sum;//则只把因子(num/divisor重复因子)赋值给sum
                }
            }
            if ((sum - num) == num) {//如果因子之和-该数等于该数,则这个数就是完数
                count ++;//计数器加一
                System.out.println("第 " + count +" 完数是: " + num);//输出完数
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("遍历全部完数所使用的时间: " + (end - start) + " 毫秒");
    }
}

5.执行结果

优化后的结果

6.说在后面

• 本人电脑是13年购买，配置一般，所以结果仅说明运行效率问题；
• 49,994,999+次遍历只用了400多毫秒，也就一眨眼的功夫，一般的算法优化对运行效率提升有限；
• int类型取值范围到21亿,代码中有多个数累加求和，很可能求和结果超出int类型范围,影响运行结果,所以建议求完数的范围不要太大.