# 204. 计数质数

<https://leetcode-cn.com/problems/count-primes/>

## 解法一：暴力（超时）

遍历从2到n的所有数，每次用一个质数检测函数检验。检测原理是看n能否整除2到n，只要有一个，n就不是质数，实际上只用检测**2到√n**即可，因为n以内的素数不会超&#x8FC7;**√n**。

```python
class Solution:
    def countPrimes(self, n: int) -> int:
        count = 0
        for i in range(2, n):
            if self.isPrime(i):
                count += 1
        return count
    
    #检验是否为质数
    def isPrime(self, n):
        i = 2
        #实际上检测能否整除[2, √n]范围即可
        #用乘法代替开平方函数，提高速度
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 1
        return True
```

## 解法二：埃拉托斯特尼筛法

伪代码，摘自维基百科：

```
Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding sqrt(n):
   if A[i] is true:
     for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n :
       A[j] := false
 
Output: all i such that A[i] is true.
```

```python
class Solution:
    def countPrimes(self, n: int) -> int:
        isPrime = [True] * (n)  #标志数组
        #筛法
        i = 2
        while i ** 2 < n:
            if isPrime[i] == True:
                for j in range(i**2, n, i):  #i², i²+i, i²+2i, i²+3i...
                    isPrime[j] = False
            i += 1
        #统计素数    
        count = 0
        for i in range(2, n):
            if isPrime[i] == True:
                count += 1
        return count
```

其实用sqrt速度也差不多，还简洁：

```python
class Solution:
    def countPrimes(self, n: int) -> int:
        isPrime = [True] * (n)  #标志数组
        #筛法
        for i in range(2, int(math.sqrt(n))+1):
            if isPrime[i] == True:
                for j in range(i**2, n, i):
                    isPrime[j] = False
        #统计素数    
        count = 0
        for i in range(2, n):
            if isPrime[i] == True:
                count += 1
        #print(isPrime)
        return count
```


---

# 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://cai-sen-se.gitbook.io/leetcode/201-400/204.-ji-shu-zhi-shu.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.