1、概念
首先我們理解一下，什么叫做完美數？
問題描述：若一個自然數，它所有的真因子（即除了自身以外的約數）的和恰好等于它本身，這種數叫做完全數。簡稱“完數”
例如，
6=1+2＋3
28=1＋2＋4＋7＋14
496=1+2+4+8＋16+31+62＋124+248
8128=1＋2＋4+8＋16＋32+64＋127+254＋508+1016＋2032+4064
按照完數的定義，其實用程序求解完數并不是太難，先求解出這個數的所有真因子，然后相加，判斷是否等于它本身即可。但是，在這個數很小的時候，沒有什么問題，一旦這個數字超過一定的數值，那么問題就來了，程序的執行效率就會變得低下。
我們優化程序的算法邏輯，往往會考慮一個問題，怎么高效的利用計算機的特性？在它所定義的算法中，有沒有大量重復的無用功呢？沿著這樣的思路去考慮這個問題，我們會很快得到另外的一種解決方案。
2、說明
2.1分析
在這里，我們會不會很容易就想到，之前我們提到過的分解因式？是的，在解決完美數的時候，我們會用到分解因式。一般來說，求解完美數會經過三個步驟：
1.求出一定數目的質數表
2.利用質數表求指定數的因式分解
3.利用因式分解求所有真因數和，并檢查是否為完美數
2.2難點
初看之下，第一步和第二步是沒什么問題的，我們在前面的兩篇文章中已經探討過了，不清楚的同學可以查看。
重點是在第三步，如何求真因數和？方法很簡單，要先知道將所有真因數（有不清楚真因數概念的同學，去看看）和加上該數本身，會等于該數的兩倍（有些同學不知道，現在應該也知道了吧？），例如：
|
1
|
2 * 28 = 1 + 2 + 4 + 7 + 14 + 28 |
事實上，這段等式可以轉換為：（代碼輸入錯誤，我用截圖好了）
發現沒有？2和7都是因式分解得到的，那么，程序是不是有了簡化的地方？
2.3結論
只要求出因式分解，就可以利用循環求得等式后面的值，將該值除以2就是真因數和了；等式后面第一眼看時可能想到使用等比級數公式來解，不過會使用到次方運算，可以在進行讀取因式分解陣列時，同時計算出等式后面的值。
3、代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
import java.util.arraylist; // 求解完美數 public class perfectnumber { // 傳入一個值，求解至少多少個完美數 public static int[] lessthan(int number) { int[] primes = prime.findprimes(number); arraylist list = new arraylist(); for(int i = 1; i <= number; i++) { int[] factors = factor(primes, i); if(i == fsum(factors)) list.add(new integer(i)); } int[] p = new int[list.size()]; object[] objs = list.toarray(); for(int i = 0; i < p.length; i++) { p[i] = ((integer) objs[i]).intvalue(); } return p; } // 分解因式 private static int[] factor(int[] primes, int number) { int[] frecord = new int[number]; int k = 0; for(int i = 0; math.pow(primes[i], 2) <= number;) { if(number % primes[i] == 0) { frecord[k] = primes[i]; k++; number /= primes[i]; } else i++; } frecord[k] = number; return frecord; } // 因式求和 private static int fsum(int[] farr) { int i, r, s, q; i = 0; r = 1; s = 1; q = 1; while(i < farr.length) { do { r *= farr[i]; q += r; i++; } while(i < farr.length - 1 && farr[i-1] == farr[i]); s *= q; r = 1; q = 1; } return s / 2; } public static void main(string[] args) { int[] pn = perfectnumber.lessthan(1000); for(int i = 0; i < pn.length; i++) { system.out.print(pn[i] + " "); } system.out.println(); } } |
總結
以上就是本文關于java語言求解完美數代碼分析的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出！
原文鏈接：http://blog.csdn.net/ljtyzhr/article/details/38962569
