整数的因子分解

package com.viking.divide;

/**
 * 
 * @author viking
 * 
 *         求整数的因子分解 比如12可以分解为 
 *         12=12
 *         12=6*2
 *         12=4*3 
 *         12=3*4 
 *         12=3*2*2 
 *         12=2*6
 *         12=2*2*3 
 *         12=2*3*2
 * 
 *         基本思路 用分治的思想 
 *         n=x1*x2*x3*x4.....xm 
 *         n=x1*(x2*x3*x4.....xm)
 *         n=x2*(x1*x3*x4.....xm) 
 *         ... 
 *         n=x1*x2*(x3*x4.....)
 * 
 *         f(n)=1+f(n/x1)+f(n/x2)+f(n/x3)+.....+f(n/xm)
 *         递归条件当n为素数时，f(n)=1
 */
public class Factor {
	public static void main(String[] args) {
		int n = 100;
		System.out.println("sum=" + factor(n, n + "="));
	}

	public static int factor(int n, String path) {		
		// n=n*1;
		int sum = 1;
		// 求 n的所有因子,但是一个数的最大因子最大是该数的一般
		int m=n/2;
		for (int i = 2; i <= m; i++) {
			if (n % i == 0) {
				// i是n的因子
				sum += factor(n / i, path + i + "*");
			}
		}
		// print itself
		System.out.println(path + n);
		return sum;
	}
}

学习中，如果是单纯的求因子分解的个数，可以缓存每个因子的结果，这样可以减少计算量