1.埃氏筛

埃氏筛是一种很好理解且常用的求质数方法，其原理是:枚举2~n，再把这些数的倍数标记为合数，最后输出没有被标记的数，这些数就是质数，埃氏筛是一种较为高效的方法，时间复杂度为$O(nlog(log(n)))$，最多可处理$10^{7}$以内的质数。

代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
int n,p[10000001];
bool f[10000001];
void prime(int n){
	for(int i=2;i<=n;i++){
		if(f[i])continue;
		for(int j=2*i;j<=n;j+=i)f[j]=true;
	}
	return;
}
int main(){
	cin>>n;
	//freopen("prime.in", "r", stdin);
	//freopen("prime.out", "w", stdout);
	prime(n);
	for(int i=2;i<=n;i++)if(!f[i])cout<<i<<" ";
	return 0;
}

2.欧拉筛

欧拉筛法（又称线性筛法）是一种高效的素数筛选算法，其核心思想是确保每个合数仅被其最小质因子筛除一次，从而实现线性时间复杂度O(n) ，最多可以处理$10^{8}$以内的质数

代码如下： ‌

#include<iostream>
#include<cstdio>
using namespace std;
int n,p[10000001];
bool f[10000001];
void prime(int n){
	int k=0;
	for(int i=2;i<=n;i++){
		if(!f[i])p[++k]=i;
		for(int j=1;j<=k;j++){
			if(p[j]*i>n)break;
			f[p[j]*i]=true;
			if(i%p[j]==0)break;
		}
	}
	return;
}
int main(){
	cin>>n;
	//freopen("prime.in", "r", stdin);
	//freopen("prime.out", "w", stdout);
	prime(n);
	for(int i=2;i<=n;i++)if(!f[i])cout<<i<<" ";
	return 0;
}