觀前提醒：

1. 我預設大家已經先思考並分析過題目，沒啥想法才開始 google 找解題靈感。若無，建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法。
2. 承上，既然已經有思考過了，那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了，那我可能解題想法 & 心得的部分就不會寫太多，免得干擾你的思考。
3. 所有解法都是已經取得系統的 Accepted，但或許不是最優解法，請多包涵。
4. 若對於解法不太懂，可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
5. 最後，歡迎在下面留言指教~教學相長才會進步歐~

題目

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

解題想法

1. 先建立起一個確認該數字是否為質數 "isPrime()" 的 function。
2. 然後用一個 for 迴圈包住他，把 1~n 的數字，通通丟到 "isPrime()" 裡面做確認。
3. 若該數字是質數，則質數的數量 + 1
4. 回傳質數的數量

CODE

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
  let countOfPrime = 0;
  for (let i = 1; i < n; i++) {
    if (isPrime(i)) countOfPrime++;
  }
  return countOfPrime;

  function isPrime(a) {
    if (a <= 1) return false;
    // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
    // to avoid repeatedly calling an expensive function sqrt().
    for (let x = 2; x * x <= a; x++) {
      if (a % x === 0) {
        return false;
      }
    }
    return true;
  }
};

心得

這個 Easy 題，確實也是需要花點腦筋來思考的，尤其是撰寫 isPrime(a) 這個 function 時，小弟也參考了維基百科中，質數裡面的測試質數與整數分解這個章節，裡面的試除法給了我不少靈感，便採取此一方式來撰寫我的演算法~

謝謝大家的收看，LeetCode 小學堂我們下次見~