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)"

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

This is really useful, thanks!