The challenge
Given a positive number n > 1 find the prime factor decomposition of n. The result will be a string with the following form :
"(p1**n1)(p2**n2)...(pk**nk)"
where a ** b
means a
to the power of b
with the p(i) in increasing order and n(i) empty if n(i) is 1.
Example: n = 86240 should return "(2**5)(5)(7**2)(11)"
The solution in Java code
Option 1:
public class PrimeDecomp { public static String factors(int lst) { String result = ""; for (int fac = 2; fac <= lst; ++fac) { int count; for (count = 0; lst % fac == 0; ++count) { lst /= fac; } if (count > 0) { result += "(" + fac + (count > 1 ? "**" + count : "") + ")"; } } return result; } }
Option 2:
public class PrimeDecomp { public static String factors(int n) { String result = ""; int cur = n; for(int i = 2; i<=cur; i++){ int ct = 0; while(cur%i == 0){ ct += 1; cur = cur/i; } if(ct == 1) result = result + "(" + i + ")"; else if(ct > 1) result = result + "(" + i + "**" + ct + ")"; } return result; } }
Option 3:
import java.util.Map; import java.util.TreeMap; import java.util.stream.Collectors; public class PrimeDecomp { public static String factors(int n) { Map<Integer, Integer> factorsMap = new TreeMap<>(); recursiveDecompose(n, factorsMap); return factorsMap.entrySet().stream() .map(entry -> "(" + entry.getKey() + (entry.getValue() != 1 ? "**" + entry.getValue() : "") + ")") .collect(Collectors.joining()); } private static void recursiveDecompose(int n, Map<Integer, Integer> factorsMap) { if (n == 1) { return; } for (int i = 2; i <= n; i++) { if (n % i == 0) { updateFactors(factorsMap, i); recursiveDecompose(n / i, factorsMap); return; } } } private static void updateFactors(Map<Integer, Integer> factorsMap, int i) { if (!factorsMap.containsKey(i)) { factorsMap.put(i, 1); } else { factorsMap.put(i, factorsMap.get(i) + 1); } } }
Test cases to validate our solution
import static org.junit.Assert.*; import org.junit.*; public class PrimeDecompTest { @Test public void testPrimeDecompOne() { int lst = 7775460; assertEquals( "(2**2)(3**3)(5)(7)(11**2)(17)", PrimeDecomp.factors(lst)); } }
Additional test cases
import static org.junit.Assert.*; import org.junit.Test; public class prDecompTest { private static void testing(int n, String exp) { System.out.println("Testing " + n); String ans = PrimeDecomp.factors(n); System.out.println("Actual " + ans); System.out.println("Expect " + exp); assertEquals(exp, ans); System.out.println("#"); } @Test public void test() { testing(7775460, "(2**2)(3**3)(5)(7)(11**2)(17)"); testing(7919, "(7919)"); testing(17*17*93*677, "(3)(17**2)(31)(677)"); testing(933555431, "(7537)(123863)"); testing(342217392, "(2**4)(3)(11)(43)(15073)"); testing(35791357, "(7)(5113051)"); testing(782611830, "(2)(3**2)(5)(7**2)(11)(13)(17)(73)"); testing(775878912, "(2**8)(3**4)(17)(31)(71)"); testing(483499306, "(2)(41**2)(143813)"); } private static int randInt(int min, int max) { return (int)(min + Math.random() * ((max - min) + 1)); } public static String factors232(int lst) { String result = ""; for (int fac = 2; fac <= lst; ++fac) { int count; for (count = 0; lst % fac == 0; ++count) { lst /= fac; } if (count > 0) { result += "(" + fac + (count > 1 ? "**" + count : "") + ")"; } } return result; } @Test public void test1() { System.out.println("Random Tests"); for (int i = 0; i < 50; i++) { int n = randInt(100000, 77587891); String exp = factors232(n); testing(n, exp); } } }
This is really useful, thanks!