返回Java中的素数因子串
我知道这是一个经典问题。 我用Java解决了它。 我的解决方案如下。 但是，当我在codefights.com中使用此解决方案时，它超出了执行时间限制。 如果有人能以任何可能的方式向我提出改进此代码的建议，我将不胜感激。 请随意批评我的代码，以便我可以提高我的编码技能。 谢谢
你得到的数字是n。
返回n作为其主要因素的乘积。
例
对于n = 22，输出应为“2 * 11”。
对于n = 120，输出应为“2 * 2 * 2 * 3 * 5”。
对于n = 17194016，输出应为“2 * 2 * 2 * 2 * 2 * 7 * 59 * 1301”。
[输入]整数n
小于109的整数。[输出]字符串
由*符号分割的n的素数因子。 主要因素应该是增加的顺序。
解决方案（JAVA）：
public String primefactors(int n) { String factors = ""; for (int i = 2; i <= n / 2; i++) { if (isPrime(i)) { while (n % i == 0) { n /= i; if (isPrime(n) && n != 1) { factors = factors + Integer.valueOf(i).toString() + "*" + Integer.valueOf(n).toString(); break; } else if (n == 1) factors = factors + Integer.valueOf(i).toString(); else factors = factors + Integer.valueOf(i).toString() + "*"; } } } return factors; } public boolean isPrime(int n) { boolean prime = true; if (n == 1) return false; else if (n % 2 == 0 && n!=2) return false; else if (n % 3 == 0 && n!=3) return false; else { for (int j = 2; j < n / 2; j++) { if (n % j == 0) { return false; } } } return prime; } 由于n小于固定数（109），只需使用包含所有prims <= 109的表，而不是动态生成它们。 或至少首先使用erathostenes或atkin的筛子生成prims。 硬编码表会更好，但使用筛子动态生成表格也会加快速度。 您实现的isPrime()函数是性能杀手。
函数primefactors isPrime()在primefactors被调用太多次。 例如， i == 2并且n有许多除数2 。 热门电话(isPrime(i)) 。 但是，在循环内部while (n % i == 0) ，在每次除以n /= 2;后检查isPrime(n) n /= 2; 。 因此，如果初始n为100则函数isPrime()被调用50 ，而下一个循环被调用25 。 这没有任何意义。 我认为这是最大的问题，因为即使isPrime在线性时间内工作，在内部循环中多次调用它也是太多了。
在两种情况下可以从循环中退出： n在除法之后等于1 ，或者如果i大于sqrt(n)则n肯定是素数。
public String primefactors(int n) { String factors = ""; int max_divisor = sqrt(n); for (int i = 2; i <= max_divisor; i++) { if (isPrime(i)) { while (n % i == 0) { n /= i; if (n == 1) factors = factors + Integer.valueOf(i).toString(); else factors = factors + Integer.valueOf(i).toString() + "*"; } max_divisor = sqrt(n); } } // check for the last prime divisor if (n != 1) factors = factors + Integer.valueOf(n).toString(); return factors; }
即使在改进之后（并且sqrt(n)作为sqrt(n)中的最大限制），您的算法将具有线性复杂度O(n) ，因为对于i ，最多有sqrt(n)循环，并且对于i ，最大探针数量in isPrime也是sqrt(n) 。
是的，通过为isPrime()选择更好的算法可以做得更好。 即使您不允许使用硬编码的素数表，也可以在运行时生成这样的查找表（如果有足够的内存）。 因此，可以使用按升序组织的自动生成的素数列表来探测最大为sqrt(n ）的给定数量。 如果i变得大于sqrt(n)则表示找到了下一个素数，并且它应该附加到查找表中，并且isPrime()应该返回true 。
例
假设isPrime被调用为113 。 在那一刻，查找表有一个以前的素数列表： 2,3,5,7,11,13... 因此，我们尝试将113从该列表中的项目除以sqrt(113) （ while (i <= 10) ）。 在尝试2,3,5,7之后，列表11上的下一个项目太大，因此将113添加到素数列表中，并且该函数返回true 。
在最坏的情况下，其他算法可以提供更好的性能。 例如，Eratosthenes筛或Atkin筛可以用于有效预先计算的素数列表，直到给定n具有最佳O(n)复杂度以实现最佳实施。 在这里你需要找到所有素数到sqrt(n) ，所以需要O(sqrt(n))来生成这样的列表。 一旦生成了这样的列表，您需要尝试按数字划分您的输入是最多需要sqrt(n)探测的列表。 因此，算法复杂度为O(sqrt(n)) 。 但是，假设您的输入为1024 ，即2的幂为10 。 在这种情况下，第一个算法会更好，因为它不会去大于2素数。
你真的需要函数isPrime（）吗？
灵活思考如果我们仔细观察，您似乎不必在某个范围内搜索所有素数。 您只需要找到一个给定整数的所有素数除数。 但是，如果我们尝试将n除以范围内的所有整数到sqrt(n) ，这也是很好的解决方案。 即使这样的整数不是素数，它也会因条件n % i == 0而被跳过，因为所有低于被测整数的质数都已从n删除，因此简单的模块化除法与isPrime()相同。 O(sqrt(n))复杂度的完整解决方案：
public String primefactors(int n) { String factors = ""; int max_divisor = sqrt(n); for (int i = 2; i <= max_divisor; i++) { while (n % i == 0) { n /= i; max_divisor = sqrt(n); if (n == 1) factors = factors + Integer.valueOf(i).toString(); else factors = factors + Integer.valueOf(i).toString() + "*"; } } // check for the last prime divisor if (n != 1) factors = factors + Integer.valueOf(n).toString(); return factors; }
也可以分割函数以避免if (n == 1)检查内循环，但是它不会改变算法的复杂性。