素數

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整除。因此，你不需要除以偶數。此外，你不會有一個大于其價值一半的因素。如果你想讓它變得復雜，那就用第一題的補充概念吧。