認識 JavaScript (十一)

※ 質數判斷

• 質數：除了1跟本身,沒有其他的因數。
• 因數：可以整除的數字。
• 用到的運算符號：「%」 mod 求餘數。
• 整除： mod完為0，沒有餘數。

※ 使用for迴圈

let x = 97 // 可以修改成其他數值來測試
//flag標記
let isNotPrime = false //先判斷是不是質數
for (let i = 2; i <= x - 1; i = i++) {
  if (x % i === 0) {
    isNotPrime = true
    break // 如果找到能整除的因數，直接結束迴圈
  }
}
if (isNotPrime) {
  console.log(`${x}不是質數`)
} else {
  console.log(`${x}是質數`)
}

說明：

為什麼要用 i <= x - 1 的判斷條件是因為：

1. 不需要檢查 x 本身：任何數除以自己都會等於1，所以這不是質數判斷所需要的。
2. 不需要檢查1：任何數除以1都等於其本身，這也不會對判斷質數有所幫助。

※ i <= x - 1改成開根號的寫法

let x = 23 // 可以修改成其他數值來測試

//flag標記

let isNotPrime = false //先判斷是不是質數

for (let i = 2; i <= Math.sqrt(x); i++) {

if (x % i === 0) {

isNotPrime = true

break // 如果找到能整除的因數，直接結束迴圈

}

}

if (isNotPrime) {

console.log(`${x}不是質數`)

} else {

console.log(`${x}是質數`)

}

說明：

為什麼要改成開根號的寫法是因為：

1. Math.sqrt(x) 會計算 x 的平方根。
2. 迴圈會從 2 運行到 x 的平方根，減少了要依序驗證的範圍，也提高了判斷質數的效率。

※ 改成while迴圈

let x = 67
// flag標記
let isNotPrime = false //先判斷是不是質數
let i =2 // 起始值
while (i <= x - 1) {
 if (x % i === 0) {
    isNotPrime = true
    break //運算效率會比別人快
  }
  i++ // 等同於 for 迴圈中的 i++
}
if (isNotPrime) {
  console.log(`${x}不是質數`)
} else {
  console.log(`${x}是質數`)
}