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!