题目:打印出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类型范围,影响运行结果,所以建议求完数的范围不要太大.
网友评论