Primes in Numbers in Java

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)"
Code language: JSON / JSON with Comments (json)

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)"
Code language: JavaScript (javascript)

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; } }
Code language: Java (java)

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; } }
Code language: Java (java)

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); } } }
Code language: Java (java)

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)); } }
Code language: Java (java)

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); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
1 Comment
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
Jack
Jack
10 months ago

This is really useful, thanks!