Print All Factors Of a Number

Given a positive number. Find all unique combinations of factors that constitute the number.

Note that we are not asking for only prime factors but any factors including primes. For example, given number n=12 can be factorize into 12 * 1, 6 * 2, 4 * 3, 3 * 2 * 2.

Note that for any number n, the number n itself is a factor which can constitute n by n * 1. Next we should try to factorize using 2. So, naturally we will try to completely divide the number n by 2 and get the factors for n/2 to get final factorization. Then try to divide with 3 and get factorization of n/3 and so on.

fact(n) = n * 1
fact(n) = fact(n/factor) * factor, for factor = 2, 3, 4, ...,n-1

We can easily implement this recurrence relation using a recursion. Below is a simple implementation of the above relation.

public static void printFactors(int number) {
	System.out.println("factors: ");
	printFactors("", number, number);
}

public static void printFactors(String expression, int dividend, int previous) {
	if (expression == "")
		System.out.println(previous + " * 1");
	for (int factor = dividend - 1; factor >= 2; --factor) {
		if (dividend % factor == 0 && factor <= previous) {
			int next = dividend / factor;
			if (next <= factor)
				if (next <= previous)
					System.out.println(expression + factor + " * " + next);
			printFactors(expression + factor + " * ", next, factor);
		}
	}
}