204. Count Primes.md

204. Count Primes

思路

思路一

不断循环，判断某个数是否是素数，判断思路：
对于大于1的整数n，若n能被2、3...sqrt(n)中任意一个数整除，则n不是素数，否则是素数。
时间复杂度O(n^(3/2)), 空间复杂度O(1)

思路二*(厄拉多塞筛法)

求解有多少个小于某个数的素数的快速方法--厄拉多塞筛法(参考博客)
西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。
具体操作：先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。
时间复杂度O(n)，空间复杂度O(n)

C++

思路一

class Solution {
private:
    bool isPrime(int n){
        if(n < 2) return false;
        for(int i = 2; i <= sqrt(n); i++)
            if(n % i == 0) return false;
        return true;
    }
public:
    int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i < n; i++)
            if(isPrime(i)) count++;
        return count;
    }
};

思路二

class Solution {
public:
    int countPrimes(int n) {
        vector<bool>Prime(n + 1, true);
        int res = 0;
        for(int i = 2; i < n; i++){
            if(Prime[i]){
                res++;
                for(int j = i; j <= n / i; j++) Prime[i*j] = false;
            }
        }
        return res;
    }
};