【leetcode】204. Count Primes

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

【豚豚】可恶！被骗去洗澡了啊啊啊啊啊啊啊啊啊啊啊啊！！

---

思路：
Discuss区中有人在评论区发的一个gif图（如下图），很直观。

---

代码实现：

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2){
            return 0;
        }
        if (n == 3){
            return 1;
        }
        
        vector<bool> isPrime(n+1, 1);
        isPrime[2] = 1;
        isPrime[3] = 1;
        int ret = n-1-1;
        for (int i = 2; i < sqrt(n); ++i){
            if (isPrime[i] == 1){
                for (int j = 2; j*i < n; ++j){
                    if (isPrime[j*i] == 1){
                        isPrime[j*i] = 0;
                        --ret;
                    }
                    
                }
            }
        }
        
        return ret;
    }
};

---

参考：
https://leetcode.com/problems/count-primes/discuss/57588/My-simple-Java-solution