檢查質數

algorithm

質數（Prime Number）的定義：

如果正整數 N 的因數只有 1 和 N ，而且 1 和 N 不相等，則正整數 N 為質數。

檢查條件

  • 質數必為正整數且大於 1
    因為 1 的因數只有 1 ，不符合定義
  • 對某數 X 開根號並命名為 sqrtX ，小於 sqrtX 的所有正整數若不能整除 X ，則 X 必為質數
    舉例： 100 的因數有：
    1 x 100
    2 x 50
    4 x 25
    5 x 20
    10 x 10
    20 x 5
    25 x 4
    50 x 2
    100 x 1
    超過開根號後的數皆為重複，故檢查開根號前的數字是否整除即可。

流程圖

input：欲檢查的數
divisor：除數

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isPrime(x) {

	// 質數必為大於 1 正整數
	if(x <= 1 || x % 1 != 0) {
		return false;
	}

	// 測試小於其正平方根的整數是否為因數
	for(let i = 2; i < Math.sqrt(x); i++) {
		if(x % i === 0) return false;
	}

	return true;
  
}