【基础数学--埃氏筛】204. 计数质数

题目描述

给定整数 n ，返回所有小于非负整数 n 的质数的数量 。

示例：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解题思路

概念：

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

根据概念与题意，自然而然想到从(1, n)的开区间上暴力搜索所有素数(质数)。

判断素数的逻辑从概念上 “除了1和它本身以外不再有其他因数” 上出发，有：

bool isPrime(int x){
    
	if(x < 2) return false;
	for(int i = 2; i < x; ++i){
    
		if(x % i == 0) return false;
	}
	return true;
}

上述判断算法时间复杂度为O(n)，嵌入到外层开区间(1, n)的外层循环内，算法整体时间复杂度直接来到O(n^2)，当n很大时直接超时。

枚举改良

isPrime()函数中搜索开区间(1, x)中x的因数，假设i是x的因数，那么x / i必定也是x的因数。并且只有当i == sqrt(x)时，有i == x / i，其他情况下，两个因数分布在sqrt(x)左右两侧。

进一步思考，判度素数只需找到一个因数即可返回false，因此我们搜索区间可以缩小到[2, sqrt(x)]（查找较小的因数）。整体时间复杂度减小到O(n^1.5)。

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

埃氏筛

改良后的枚举法时间复杂度还是很大，在C++编译环境下提交依旧会超时，这是因为枚举法终究是忽视区间内数字内在规律的暴力搜索方法。

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

仔细分析不难发现这样的规律，假如x是质数，那么x的倍数例如2x、3x、...必为合数 。因此可以这么设计算法，依旧在目标区间(1, n)搜索质数，搜索顺序遵循 由小到大。当搜索到质数时，将其区间内倍数全部标记为合数，由小到大的搜索顺序一定会把下一个质数前的所有合数全部标记。这样就大大减少了判度一个整数是否是质数的次数，进而降低时间复杂度。

其实还是有优化空间的，还是上述假设，x为质数时，2x真的需要我们标记吗?

不用！在搜索到质数2时，上面的2x已经标记过了，搜索到x时再标记2x反而增加了从不必要的操作。

代码实现

改良枚举：

class Solution {
    
public:
    bool isPrime(int x) {
    
        for (int i = 2; i * i <= x; ++i) {
    
            if (x % i == 0) {
    
                return false;
            }
        }
        return true;
    }

    int countPrimes(int n) {
    
        int ans = 0;
        for (int i = 2; i < n; ++i) {
    
            ans += isPrime(i);
        }
        return ans;
    }
};

在n == 5000000时报超出时间限制！

埃氏筛：

class Solution {
    
public:
    int countPrimes(int n) {
    
        int cnt = 0;
        vector<int> isPrime(n, 1);
        for(int i = 2; i < n; ++i){
    
            if(isPrime[i]){
    
                cnt++;
                if((long long) i * i < n){
    
                    for(int j = i*i; j < n; j += i){
    
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return cnt;
    }
};

运行结果：