Java小例子：分解質因數

這個例子演示如何利用遞歸來完成分解質因數。

import　java.util.List;

import　java.util.ArrayList;

/**

　*　分解質因數

　*/

public　class　GetFactor　{

　　　　public　static　void　main(String[]　args)　{

　　　　　　　　List<Long>　factors　=　getFactors(5555566666L,　2);

　　　　　　　　System.out.println(factors);

　　　　}

　　　　/**

　　　　　*　通過遞歸實現分解質因數

　　　　　*

　　　　　*　@param　n　　　　　　要分解的數字

　　　　　*　@param　factor　起始因子

　　　　　*

　　　　　*　@return　分解結果

　　　　　*/

　　　　private　static　List<Long>　getFactors(long　n,　long　factor) 　{

　　　　　　　　//　不斷增大　factor　直到能整除n

　　　　　　　　while　(n　%　factor　!=　0　&&　factor　<　n)　 {

　　　　　　　　　　　　//　得到　2,3,5,7,9,11,13,...

　　　　　　　　　　　　factor　=　factor　<　2　?　2　:　factor　==　2　? 　3　:　factor　+　2;

　　　　　　　　}

　　　　　　　　List<Long>　result;

　　　　　　　　if　(factor　>=　n)　{　　//　因子已經漲到和　n　一樣大，說 明　n　本身就是因子。這時遞歸完成。

　　　　　　　　　　　　result　=　new　ArrayList<Long>();

　　　　　　　　}　else　{　　　　　　　　　　　　//　因子能夠整除　n，於是繼 續分解除以因子後的結果

　　　　　　　　　　　　result　=　getFactors(n　/　factor,　factor);　//　向 下遞歸

　　　　　　　　}

　　　　　　　　result.add(factor);

　　　　　　　　return　result;

　　　　}

}