题目描述
统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 106
解题思路
枚举-略
埃式筛-如果 x 是质数，那么大于 x 的倍数 2x,3x,… 一定不是质数，设 isPrime[i] 表示数 i是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数。继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。时间复杂度O(nloglogn)。
leetcode官方题解
源码
class Solution {
public:
bool isPrime(int n)
{
if(n<2)return false;
if(n==2||n==3||n==5||n==7)return true;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)return false;
}
return true;
}
int countPrimes(int n) {
/*
int ans=0;
for(int i=0;i<n;i++)
{
if(isPrime(i))ans++;
}
return ans;
*/
//埃式筛-get 新知识
vector<int> isPri(n,1);
int ans=0;
for(int i=2;i<n;i++)
{
if(isPri[i])
{
ans++;
if((long long)i*i<n)
{
for(int j=i*i;j<n;j+=i)
{
isPri[j]=0;
}
}
}
}
return ans;
}
};
题目来源
来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
