Primes in numbers（5Kyu） - 图1

题目

Given a positive number n > 1 find the prime factor decomposition of n. The result will be a string with the following form :”(p1n1)(p2n2)…(pknk)” 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. 给定一个正数n>1，求n的素因子分解。结果将是一个具有以下形式的字符串：“（p1n1）（p2n2）…（pknk）”，其中ab表示a与p（i）的幂成正比，如果n（i）为1，则n（i）为空。

例子

n = 86240 should return “(25)(5)(72)(11)” 86240=2 x 2 x 2 x 2 x 2 x 5 x 7 x 7 x 11 —> (25)(5)(72)(11)

原题链接

分析

分解质因数问题，可以从2开始遍历到n,判断n是否可以整除i,可以整除计数器+1，n = n/i,不可以整除向下遍历，最后返回结果的时候先判断计数器是否为0，0代表当前的i不能被n整除即不是n的因子，不为0代表是因子，看看计数器个数判断输出格式，搞定。

我的解法

  1. public class PrimeDecomp {
  3.     public static String factors(int n) {
  4.         String result = "";
  5.         for (int i = 2; i <= n; i++) {
  6.             int count = 0;
  7.             while (n % i == 0) {
  8.                 count++;
  9.                 n /= i;
  10.             }
  11.             result += count == 0 ? "" : count > 1 ? "(" + i + "**" + count + ")" : "(" + i + ")";
  12.         }
  13.         return result;
  14.     }
  16. }

参考解法

  1. public class PrimeDecomp {
  3.     public static String factors(int lst) {
  4.         String result = "";
  5.         for (int fac = 2; fac <= lst; ++fac) {
  6.             int count;
  7.             for (count = 0; lst % fac == 0; ++count) {
  8.                 lst /= fac;
  9.             }
  10.             if (count > 0) {
  11.                 result += "(" + fac + (count > 1 ? "**" + count : "") + ")";
  12.             }
  13.         }
  14.         return result;
  15.     }
  16. }

提升

  1. 这道题比较简单，如果想提高解算效率，可以做个素数表，然后在素数表中遍历看看是否是n的因子，写起来比较繁琐就是了
  2. 通过 +"" 拼接字符串其实没有 String.format("(%d)", n) 或者 new StringBuilder().append("") 的效率高。执行一次字符串 + ,相当于 str = new StringBuilder(str).append("a").toString(）
  3. 字符串的加号 + 方法， 虽然编译器对其做了优化，使用 StringBuilder 的 append 方法进行追加，但是每循环一次都会创建一个 StringBuilder 对象，且都会调用 toString 方法转换成字符串，所以开销很大（时间、空间）
  4. StringBuilder 每次字符串拼接都只是扩展内部char数组，只生产一个最终的string，所以这种效率最高,

StringBuffer StringBuffer与StringBuilder相比只是多加了个synchronized，所以在单线程的情况下相差不大,

  1. 拼接字符串性能：StringBuilder>StringBuffer>StringUtils.join>concat>+