---
description: return、continue、break 差異 / 想好 pattern 再寫 code / 先存值就不會重覆算到 / 複習
---

# # 204 Count Primes (有圖)

[LeetCode](https://leetcode.com/problems/count-primes/)    這題想了很久...

```
Count the number of prime numbers less than a non-negative number, n
input: number
output: how many 質數
```

首先我們來想質數的特性

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrVg08fI3-GMwgNCoEp%2F-LrVhKYfh5NHV9MIw2Bd%2Fmaxresdefault.jpg?alt=media\&token=34b5dcce-690f-447f-b16a-08441fa36180)

```
質數 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29...]
```

### 比較笨想法

* \[2, 3] 是質數
* \> 3 就是每次 + 2 檢查是否除的進

```
num = 11
用 3 5 7 9 去得餘數是否為零
11%3 != 0
11%5 != 0
11%7 != 0
11%9 != 0
都除不進所以 11 是質數
```

```
function isPrime(num){
    if(num == 2 || num == 3){
        return true;
    }
    if(num%2 == 0){
        return false
    }
    let divisor = 3;
    // 這邊比較笨 因為就會 %3 % 5 %7 %9 %11 % 13 %15
    // 而不是 %3 %5 %7 %11 %13 %17
    while(divisor< num){
        if(num%divisor==0){
            return false
        }
        divisor += 2;
    }
    return true
}
```

### 一樣的想法取解這題取得質數有幾個

```
n = 14
3 5 7 9 11 13

// i 9
// j 3 5 7 


// i 11
// j 3 5 7 9

// i 13
// 3 5 7 9 11


// i 15
// j 3 5 7 9 11 13
```

```
var countPrimes = function(n) {
// n = 3的時候，才會出現第一個比n小的質數2
if(n < 3) return 0;

var count = 1;
// 加快速度，所以跳過2的倍數
for(var i = 3 ; i < n ; i+=2){
    var flag = true;
    // 判斷i是不是質數
    for(var j = 3 ; j*j <= i; j+=2){
        if(i%j == 0){
            // i能被比自己小的數除盡，表示i不是質數
            flag = false; 
            break;
        }
    }

    if(flag) count++;
}

return count;
};
```

### 改善

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrViDkIhIGV55TnEGfR%2F-LrVk9IdkoMVn8gQYmLn%2F1.jpg?alt=media\&token=6404c2db-2cb0-4873-aa31-7add29b8184d)

* 其實重覆的值就不用再算一次，例如 15 再 %3 時候就知道不是餘數，所以不用再 %5 算一次

```
var countPrimes = function(n) {
    if( n<3 ){ return 0; }

    var count = 0;
    var primeMap = new Array(n);
    for( var i=2;i<n;i++){
        if( primeMap[i] ){
            continue;
        }
        count++;
        for(var j=i;j<n;j=j+i){
            primeMap[j] = true;
        }
    }
    return count;
};
```

## 學到什麼

這題學挺多的，先是 return、continue、break 差異

#### Return

```
function print(nums){
    return "return";
    // 以下不會執行
    for(let i = 0; i< nums; i++){

    }
}
```

#### Break

```
function print(nums){
    for(let i = 0; i< nums; i++){
        
        if(i == 2){
            break
        }
        console.log("i: ", i)
    }
} 
print(10);
// 0 1 2
```

#### Continue

```
function print(nums){
    // 以下不會執行
    for(let i = 0; i< nums; i++){
        
        if(i == 2){
            continue;
        }
        console.log("i: ", i)
    }
} 
print(5);
// 0 1 3 4 5 
```

再來就是可以先存值就不用重算一次
