LeetCode 204. Count Primes使用Siev

前两天腾讯笔试碰到这个题，还很傻的采用了传统方法，今天刷题碰到类似的题，发现一个很巧妙的算法：Sieve of Eratosthenes，详情见wikipedia吧

直接贴代码了：

class Solution {
public:
//Sieve of Eratosthenes，算法时间复杂度nloglogn
//https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    int countPrimes(int n) {
        vector<bool> prime(n,true);
        prime[0] = false;
        prime[1] = false;
        for(int i = 0; i < sqrt(n); i++)
            if(prime[i])
            {
                for(int j = i*i; j < n; j += i)
                    prime[j] = false;
            }
        return count(prime.begin(),prime.end(),true);
        
    }
};

时间复杂度的简单解释，可以认为是将n个数划分成为了sqrt(n)个小组，每个小组又分成了sqrt(n)－1个小组。最后遍历一次每个小组。O(nloglogn)