Print All Factors Of a Number - Algorithms and Problem SolvingAlgorithms and Problem Solving
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.
Note that we need the previousFactor just to keep our newly found factors smaller or equal. This will be our way to make sure we do not repeat tuples when we print all sets of factors.
Related: Efficient program to print all prime factors of a given number
Read full article from Print All Factors Of a Number - Algorithms and Problem SolvingAlgorithms and Problem Solving
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
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); } } }http://www.fitcoding.com/2014/09/15/print-all-sets-of-factors/
Note that we need the previousFactor just to keep our newly found factors smaller or equal. This will be our way to make sure we do not repeat tuples when we print all sets of factors.
- public class NumberFactors
- {
- public static void PrintFactors(int number)
- {
- printFactorsHelper("", number, number);
- }
- private static void printFactorsHelper(String currExpression, int dividend, int previousFactor)
- {
- for (int factor = dividend - 1; factor >= 2; --factor)
- {
- if (dividend % factor == 0 && factor <= previousFactor)
- {
- // found 2 factors
- int nextFactor = dividend / factor;
- // try printing only if secondfactor is smaller (i.e. descending order)
- if (nextFactor <= factor)
- {
- if (nextFactor <= previousFactor)
- {
- System.out.println(currExpression + factor + " * " + nextFactor);
- }
- }
- printFactorsHelper(currExpression + factor + " * ", nextFactor, factor);
- }
- }
- }
- }
Related: Efficient program to print all prime factors of a given number
Read full article from Print All Factors Of a Number - Algorithms and Problem SolvingAlgorithms and Problem Solving