leetcode204. Count Primes(204. 计数质数)/埃式筛

题目：204. 计数质数

Count the number of prime numbers less than a non-negative number, n.

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0 

Constraints:

• 0 <= n <= 5 * 10⁶

基本思想：埃式筛

本题其实可以依次判断小于n的数是否是质数，但是时间复杂度会达到O（n^1.5）
这里简单描述下埃式筛的思想：

• 对于一个数p而言，其倍数2p，3p， 4p，……，n肯定不是质数，这里就基于这个思想进行处理
• 定义一个大小为n的数组，标记小于n的数是否是质数
• 在判断的过程中外层循环其实从2开始，一直到$\sqrt{n}$
• 内存循环处理当前数的倍数，其实不用从2倍开始，从p倍开始就行，因为小于p倍的情况，在之前已经被其他数处理过

cpp代码

class Solution {
public:
    int countPrimes(int n) {
        if(n <= 2)
            return 0;
        vector<int> nums(n, 0);
        nums[1] = 1;
        int p = 2;  
        int res = 0;
        while(p * p < n){
            if(nums[p * p] == 0){
                int cur = p * p;
                for(int i = 0; cur + i * p < n; ++i){
                    nums[cur + i * p] = 1;
                }
            }            
            ++p;
        }
        for(int i = 1; i < n; ++i){
            if(!nums[i]){
                ++res;
            }
        }
        return res;
    }
};

python版本

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        
        # TODO:将所有的倍数标记为合数
        isPrime = [1 for i in range(n)] #初始时，将所有的数都标记为质数
        isPrime[0] = 0
        isPrime[1] = 0
        p = 2
        while p * p < n:
            if isPrime[p * p] == 1:
                cur = p * p
                while cur < n: # 将p的倍数都标记为合数
                    isPrime[cur] = 0
                    cur += p
            p += 1
        
        # TODO:统计质数的个数
        cnt = 0
        for flag in isPrime:
            if flag:
                cnt += 1
        
        return cnt