[LeetCode] Count Primes

Description:

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

使用sieve of Eratosthenes方法对质数进行筛选。

题目要求就是写出这个算法。

原理是：给出要筛数值的范围n，找出出以内的素数}。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

算法使用了STL中的count函数

algorithm头文件定义了一个count的函数，其功能类似于find。这个函数使用一对迭代器和一个值做参数，返回这个值出现次数的统计结果。

代码如下

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> prime(n, true);
        prime[0] = false, prime[1] = false;
        for (int i = 2; 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);
    }
};
// 46 ms

 附上第一次写的TLE算法。

思路比较简单，判断给定范围内每个数字是否为质数并统计。

class Solution {
public:
    int countPrimes(int n) {
        int res = 0;
        if (isPrime(n))
            res = -1;
        for (int i = 0; i <= n; i++) {
            if (isPrime(i))
                res++;
        }
        return res;
    }
    
    bool isPrime(int n) {
        if (n <= 3)
            return n > 1;
        for (int i = 2; i <= sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
};
// TLE