> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/bu-chong-6180-dao/204.-count-primes.md).

# 204. Count Primes

\# Easy

{% hint style="info" %}
要用一个特殊的方法来做会比较快。加速三部曲：

1. 遍历数组，判断每个数是不是素数
2. 遍历数组，判断每个数的时候，只除以\[ 2, sqrt(n) ]区间的数看是否能整除即可
3. 建一个一样大小的数组isPrime\[n]，初始化为true, 如果一个数是素数，则其倍数都是素数，直到遍历完所有数为止
   {% endhint %}

{% tabs %}
{% tab title="C++" %}

```cpp
class Solution {
public:
    int countPrimes(int n) {
        if(n <= 2) return 0;
        
        int count = 0;
        vector<bool> isPrime(n, true);
        for(int i = 2; i < n; i ++) {
            if(!isPrime[i]){
                continue;
            }
            count ++;
            for(int j = 2; i*j < n; j ++) {
                isPrime[i*j] = false;
            }
        }
        return count;
    }
};
```

{% endtab %}
{% endtabs %}

{% hint style="success" %}
Hightlight initilize an array with length of a variable:&#x20;

```cpp
vector<bool> isPrime(n, true);

// wrong expression
// bool isPrime[n];
```

{% endhint %}