Count Primes -- leetcode

Description:

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

基本思路：筛法

1， 2 为素数， 筛掉以2为因子的数。 即 2 * 2, 2*3, 2*4,2*5

2， 寻找到下一个未被筛除的数，如3.  再筛掉以3为因子的数。

3， 重复步骤2.

时间复杂度为O(n)

class Solution {
public:
    int countPrimes(int n) {
        vector<int> sieve(n, true);
        int count = 0;
        for (int i=2; i<n; i++) {
            if (sieve[i]) {
                ++count;
                for (int j=i+i; j<n; j+=i) {
                    sieve[j] = false;
                }
            }
        }
        return count;
    }
};

Count Primes -- leetcode

原文：http://blog.csdn.net/elton_xiao/article/details/46850175