给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
先上本题做法：（直接用2到sqrt的是过不了的，数据上来就会超时，本题采用欧拉筛，后面会介绍几种求质数的方法）
static bool is_not_p[5000001]; //偷懒写法，因为static在内存中自动用0填充，如果多次运行一定记得初始化为0
vector<int> primes;
class Solution {
public:
void isPrime(int num){
for(int i=2;i<=num;i++){
if(!is_not_p[i]){
primes.push_back(i);
// cout<<i;
}
for(int p : primes){
if(p*i>num) break;
is_not_p[p*i]=true;
if(i%p==0) break; //保证被最小因数筛掉，每个数会且只会被筛一遍
}
}
}
int countPrimes(int n) {
int ans=0;
isPrime(n);
for(int i=2;i<n;i++){
if(!is_not_p[i])
{
// cout<<i<<endl;
ans++;
}
}
return ans;
}
};
介绍一下几种素数筛，其中在复杂度上，使用欧拉筛最优：
一、朴素筛法
对于每一个i∈[2,n]，枚举[2,i-1] 中是否存在 i 的因子，有=》合数，没有=》素数
又因为对于i而言，因子一定是小于√i的，故枚举可以从 [2,i-1] 优化为 [2,√i]，因此复杂度为n√n。
时间复杂度：
O(n√n)
代码如下：
bool isPrime(int num){
for(int i=2;i<=(int)sqrt(num);i++){
if(num%i==0) return false;
}
return true;
}
二、埃氏筛法
首先将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。表中剩余的最小数字是3，他不能被更小的数整除，所以3是素数。再将表中所有3的倍数都划去。如果表中剩余的最小数字是m时，m就是素数。然后将m的倍数都划去。依次类推，反复操作，就能依次枚举出n以内的素数。
时间复杂度：
O(n*log(logn))
代码如下：
int prime[MAXN];//第i个素数
bool is_prime[MAXN+1];//is_prime[i]为true时表示i为素数
void init(){
int p=0;
for(int i=0;i<n;i++){
is_prime[i]=true;
}
is_prime[0]=is_prime[1]=false;
for(int i=2;i<=n;i++){
if(is_prime[i]){
prime[p++]=i;
for(int j=2*i;j<=n;j+=i){
is_prime[j]=false;
}
}
}
}
三、欧拉筛法（线性筛法）
欧拉筛，也叫线性筛，可以在 O（n）时间内完成对2~n的筛选。它的核心思想是：让每一个合数被其最小质因数筛到。
欧拉筛法和埃氏筛法的原理类似…但是欧拉筛法更减少了没有必要的计算，就是增加了处理：每一个被筛掉的数都必须是被它的最小质因子筛掉，为了保证这一点，增添了如下代码：
if(i % prime2[k] == 0)//确保是最小质因数
{
break;
}
时间复杂度：
O(n)
完整的算法代码如下：
bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n){
for (int i = 2; i <= n; i++){
if (!isnp[i])
primes.push_back(i);
for (int p : primes){
if (p * i > n)
break;
isnp[p * i] = 1;
if (i % p == 0)
break;
}
}
}也可以：
const int N = 1000010;
int primes[N], cnt=0; // primes[0]~primes[cnt-1]存储的是0~n中所有的质数(从小到大)
bool st[N]; // st[i] == true说明i不是质数
// 线性选法，时间复杂度：O(n)
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
参考：
https://juejin.cn/post/7085310292237762574
https://juejin.cn/post/7129079647928582175
