LeetCode //C - 204. Count Primes

题目：计算所有小于非负整数 n 的质数的数量。

解法1：暴力法

这是最简单的方法，遍历每个数字，如果它是质数，则计数器加一。

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; ++i) {
        if (isPrime(i)) {
            count++;
        }
    }
    return count;
}
 
// 判断一个数是否是质数
bool isPrime(int num) {
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            return false;
        }
    }
    return num > 1;
}

解法2：线性筛选法

线性筛选法是一个较为高效的算法，它的基本思路是：每个合数都有一个最小质因数，那么我们只需要筛掉每个数的最小质因数即可。

int countPrimes(int n) {
    bool notPrime[n];
    int count = 0;
    memset(notPrime, false, sizeof(notPrime));
    for (int i = 2; i < n; ++i) {
        if (!notPrime[i]) {
            ++count;
            if ((long long)i * i < n) {
                for (int j = i * i; j < n; j += i) {
                    notPrime[j] = true;
                }
            }
        }
    }
    return count;
}

解法3：埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更为高效的筛法，它的基本思路是：每个合数都可以表示为几个素数的乘积，那么我们只需要筛掉每个数的素数倍就可以了。

int countPrimes(int n) {
    bool notPrime[n];
    int prime[n/log(n)], cnt, i, j;
    cnt = 0;
    memset(notPrime, false, sizeof(notPrime));
    for (int i = 2; i < n; ++i) {
        if (!notPrime[i]) {
            prime[cnt++] = i;
        }
        for (j = 0; prime[j] * i < n; ++j) {
            notPrime[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
    int count = 0;
    for (int i = 2; i < n; ++i) {
        if (!notPrime[i]) {
            ++count;
        }
    }
    return count;
}

以上就是三种解法，其中解法2和解法3的时间复杂度都是O(n log log n)，而解法1的时间复杂度是O(n log n)。在实际应用中，解法2和解法3由于没有重复的计算，会比解法1更快。