Leetcode.204.Count Primes

题目

给一个整数n，求0到n一共有多少个质数。

Input：10
Output：4
Explanation: 质数2, 3, 5, 7.

思路1

常规遍历，对每个数进行判断是否为质数。中间有大量重复的计算， 时间复杂度过大。

bool countPrimesIsPrime(int n) {
    for (int i = 2; i <= sqrt(n);i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int countPrimes(int n) {
    int res = 0;
    for (int i = 2; i < n; i++) {
        if(countPrimesIsPrime(i)) {
            res++;
        }
    }
    return res;
}

思路2

逆向思维，找出不是质数的数。依次找到2的倍数，3的倍数，4的倍数等等。

int countPrimes(int n) {
    int res = n > 2 ? 1 : 0;
    vector<int> vec(n+1);
    
    for(int i=2; i <= sqrt(n); ++i) {
        if(vec[i] == 0) {
            for(int j = i*i; j < n; j += i) {
                vec[j] = 1;
            }
        }
    }
    for (int i=3; i<n; i+=2) {
        res += vec[i] == 0;
    }
    return res;
}

总结

正向不好解决的问题，可以考虑逆向思维。