Js面试算法详解

素数

Q：你将如何验证一个素数？

A：一个素数只能被它自己和1整除。所以，我将运行一个while循环并加1。（看代码示例，如果你无法理解，那这不是你的菜。先回去学习javaScript基础知识然后再回来吧。）

方法1

function isPrime(n){ var divisor = 2; while (n > divisor){ if(n % divisor == 0){  return false;  } else  divisor++; } return true;}isPrime(137); // = trueisPrime(237); // = false

Q：你能做得更好吗？

A：可以。除数一次增加1个。 在3之后我可以增加2.如果一个数可以被任何偶数整除，它将被2整除。

补充：如果你不需要把除数增加到这个数。你可以更早停止。让我在下面的步骤中解释一下（如果需要可以多读几遍）

第一步，任何数字都不能被大于它的一半的数字整除。 例如，13将永远不能被7,8,9整除……它甚至可以是偶数的一半。 例如，16将被8整除，但永远不会被9,10,11,12 ……
结论：一个数字将永远不能被一个大于其一半数值的数字整除。 所以，我们可以少循环50％。

第二步，现在，如果一个数字不能被3整除。（如果它可被3整除，那么它就不是质数）。然后，它不可以被大于其值1/3的任何数整除。例如，35不能被3整除。因此，它永远不会被大于35/3的数整除，永远不能被12, 13, 14整除…如果你取一个像36一样的偶数，它将永远不能被13, 14, 15整除。

结论： 一个数字可以被其数值的三分之一整除。

第三步，例如，你有一个数字127。127不能被2整除，因此你最多应该检查63.5。其次，127不能被3整除。因此，您将检查到127/3大约42。它不能被5整除，除数应该小于127/5大约25，而不是7。那么，我们该在哪里停下来？
结论： 除数将小于math.sqrt（N）

方法2

如果你不能理解也不用担心，别管它。如果那你不是一个研究人员就没关系。

function isPrime(n){ var divisor = 3,   limit = Math.sqrt(n); //check simple cases if (n == 2 || n == 3)  return true; if (n % 2 == 0)  return false; while (divisor <= limit) { if (n % divisor == 0)  return false; else  divisor += 2; } return true;}isPrime(137); // = trueisPrime(237); // = false

素数因子

Q：如何求出一个数的所有素数因子？
A：执行一个while循环。开始除以2，如果不能整除，记录这个除数，直到完成。

function primeFactors(n){ var factors = [],   divisor = 2; while(n>2){ if(n % divisor == 0){  factors.push(divisor);   n= n/ divisor; } else{  divisor++; }   } return factors;} primeFactors(69); // = [3, 23]

Q：运行时间复杂度是多少？ 你能做得更好吗？

A：O(n)。可以将除数从3开始，累加2。因为，如果一个数被任何偶数整除，它将被2整除。因此，你不需要除以偶数。此外，你不会有一个大于其价值一半的因素。如果你想让它变得复杂，那就用第一题的补充概念吧。