# # 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 質數
```

首先我們來想質數的特性

![](/files/-LrVhKYfh5NHV9MIw2Bd)

```
質數 = [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;
};
```

### 改善

![](/files/-LrVk9IdkoMVn8gQYmLn)

* 其實重覆的值就不用再算一次，例如 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 
```

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hannahpun.gitbook.io/leetcode-note/math/204-count-primes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.