題目:打印出1~10000以內(nèi)所有的完數(shù)

1.分析1

• 如果一個數(shù)恰好等于它的因子之和，則稱該數(shù)為“完全數(shù)”。引用百度百科-完全數(shù),如6=1＋2＋3
• 不包括數(shù)本身的所有的因子之和等于這個數(shù)，所以1不符合要求；
• 遍歷所有2~10000的數(shù)，并且嵌套遍歷0到該數(shù)范圍內(nèi)的所有預備因子，如果該數(shù)模預備因子等于0，則該預備因子為該數(shù)的因子，定義一個計數(shù)器，將所有因子累加，如果累加結(jié)果等于該數(shù)本身，即這個數(shù)為完數(shù)；
• 為了便于比較運算效率，引入System.currentTimeMillis()方法記錄遍歷前后的系統(tǒng)當前毫秒值；

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("遍歷全部完數(shù)所使用的時間: " + (end - start) + " 毫秒");} } 復制代碼

• 運行結(jié)果:

3.一點思考

• 判斷10000這個數(shù)是否是完數(shù)需要遍歷預備因子9999次，判斷9999這個數(shù)是否是完全數(shù)需要遍歷預備因子9998次，以此類推，根據(jù)等差數(shù)列求和公式需要遍歷9998*(9999 + 2) / 2 = 49,994,999次，顯然效率很低，需要進一步優(yōu)化；
• 經(jīng)過分析，完數(shù)的最大因子不會超過他本身的一半，所以可以把divisor < num改成divisor <= num / 2；
• 繼續(xù)分析，如果數(shù)num的第2因子divisor2，則(num / divisor2)也一定是num的因子，則(num / divisor2)到num之間一定不會有因子出現(xiàn)，下一步預備因子遍歷范圍縮小到divisor2 ~ (num / divisor2)；
• 繼續(xù)，如果數(shù)num的第3個因子divisor3，則(num / divisor3)也一定是num的因子，則(nmu / divisor3)到(num / divisor2)之間一定不會有因子出現(xiàn)，下一步預備因子遍歷范圍縮小到divisor3 ~ (num / divisor3)，以此類推即可；
• 將所有因子累加到計數(shù)器sum中，然后比較sum - num == num 即可，但是有個例外；
• 例如num=16，第3個因子divisor3是4，則(num / divisor3)還是4，因子4不能重復計入計數(shù)器，所以需要使用if ··· else if ···語句判斷兩種情況，分別累加因子；

4.代碼優(yōu)化

public class PerfectNumberTest {public static void main(String[] args) {int count = 0;//定義一個計數(shù)器System.out.println("1~10000范圍內(nèi)的所有完數(shù)如下:");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開根號結(jié)果不是他的因子sum = divisor + (num / divisor) + sum;//則num/divisor也一定是他的因子} else if (num % divisor == 0 && divisor == num / divisor) {//若num開根號的結(jié)果是他的因子sum = divisor + sum;//則只把因子(num/divisor重復因子)賦值給sum}}if ((sum - num) == num) {//如果因子之和-該數(shù)等于該數(shù),則這個數(shù)就是完數(shù)count ++;//計數(shù)器加一System.out.println("第 " + count +" 完數(shù)是: " + num);//輸出完數(shù)}}long end = System.currentTimeMillis();System.out.println("遍歷全部完數(shù)所使用的時間: " + (end - start) + " 毫秒");} } 復制代碼

5.執(zhí)行結(jié)果

6.說在后面

• 本人電腦是13年購買，配置一般，所以結(jié)果僅說明運行效率問題；
• 49,994,999+次遍歷只用了400多毫秒，也就一眨眼的功夫，一般的算法優(yōu)化對運行效率提升有限；
• int類型取值范圍到21億,代碼中有多個數(shù)累加求和，很可能求和結(jié)果超出int類型范圍,影響運行結(jié)果,所以建議求完數(shù)的范圍不要太大.

轉(zhuǎn)載于:https://juejin.im/post/5a34e6c4518825696f7e121c

總結(jié)

以上是生活随笔為你收集整理的Java遍历完数的一些思考的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。