需要一些数学思维，这一类题目，必须得从数学角度，才能理解算法的每一步目的。

1. 先从简单开始，判断一个数，是否为 平方和

367. 有效的完全平方数
暴力求解就可以得到，非常好理解，这提供的常用做法就是 for 循环，但是 i 是有限制的循环。

  1. var isPerfectSquare = function(num) {
  2.     if (num <= 1) {
  3.         return true;
  4.     }
  6.     for (let i = 0; i * i <= num; i++) { // important!!
  7.         if (i * i === num) {
  8.             return true;
  9.         }
  10.     }
  12.     return false;
  13. };

2. 判断一个数是否为质数

还是相同的 for 循环
image.png

  1. function isPrime(num) {
  2.     if (num <= 1) { // 1 和 负数 不是质数
  3.         return false;
  4.     }
  6.     for (let i = 2; i * i <= num; i++) { // 同样的 for 循环
  7.         if (num % i === 0) {
  8.             return false;
  9.         }
  10.     }
  12.     return true;
  13. }

正整数分为 质数 和 合数 和 1。
image.png

3. 短除法做质因数分解

image.png

  1. function getPrimeFactorOfNum(num) {
  2.     let primes = [];
  3.     for (let i = 2; i * i <= num; i++) {
  4.         if (isPrime(i)) {
  5.             if (num % i === 0) {
  6.                 num /= i;
  7.                 primes.push(i);
  9.                 if (isPrime(num)) {
  10.                     primes.push(num); // 加上最后一个商
  11.                     return primes; // 正确出口
  12.                 } else { // 不是质数
  14.                     while (num % i === 0) { // 还能继续整除
  15.                         num /= i;
  16.                         primes.push(i);
  17.                     }
  18.                 }
  19.             }
  20.         }
  21.     }
  23.     return [];
  24. }

204. 计数质数