1）传统找质数的方法（优化筛选次数）

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

• 如果要找从 $[1,1e6]$ 中的所有质数，时间复杂度很高

2）欧拉筛

• 算法思想：遍历到 $2$ 的时候，筛掉范围内所有 $2$ 的倍数（因为除了 $1$ 和自身以外，一定能被 $2$ 整除），到 $3$ 的时候，筛掉所有 $3$ 的倍数···
• 注意：如果计算 $[l,r]$ 之间出现的质数的个数？可以用前缀和的思想；当 $n$ 过大时，$i\times i$ 容易出现数组越界的错误，即可能 $RuntimeError$ ，此时要将线性筛中第二个 $for$ 中的 $j=i\times i$ 改为 $j=i+i$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int f[N]; // 下标为i时,记录1~i出现的所有质数的数量
bool vis[N]; // 是否已经访问过
int p[N]; // 用于存放素数
int idx,n; // idx是存放素数的遍历因子
void get_primes(int n)
{f[1]=0;for(int i=2;i<=n;i++){// 如果vis[i]为false才需要遍历if(!vis[i]){f[i]=f[i-1]+1; // 计算前缀和p[++idx]=i; // 是素数,存起来// 如果出现RuntimeError,将j=i+i,这样就不会数组越界for(int j=i*i;j<=n;j+=i) // 将素数i的倍数全部标记为合数,则无需遍历vis[j]=true;} else f[i]=f[i-1]; // 向下传递素数个数}
}int main()
{// 如:输入1000即打印0~1000以内的素数cin>>n;  int l,r; // 左右区间cin>>l>>r;get_primes(n);cout<<"1~"<<n<<"之间的素数分别是:";for(int i=1;i<=idx;i++) {cout<<p[i];if(i!=idx)cout<<",";}cout<<endl;cout<<l<<"~"<<r<<"所出现的素数个数为:"<<f[r]-f[l-1]<<endl;return 0;
}

• 最简单的模板

const int N=5e4+5; // 注意这里没有开到2^9,只要比sqrt(2^9)大即可
int primes[N],cnt;
bool st[N];
int ans[N],len;// 线性筛模板
void get_primes(int n) {for(int i=2;i<=n;i++) {if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]*i<=n;j++) {st[primes[j]*i]=true;if(i%primes[j]==0) break;}}
}// 为什么特判x>=N的情况?因为为了节省内存或者没必要,本题中只要保证MAXN比sqrt(理论最大值)大即可
bool is_prime(int x) {if(x<N) return !st[x];for(int i=0;primes[i]<=x/primes[i];i++)if(x%primes[i]==0)return false;return true;
}