素数筛的两个常用板子——欧筛和埃筛

直接上代码了，两个筛法很简单，就不多加赘述了

#include
#include
#define ll long long
#define pii pair
#define inf 1e9
using namespace std;
const int N = 1e8+5;
const int mod = 1e9+9;
int t, n, m;
// 欧筛
int k;
int prime[N];
int vis[N];
void Ou_init(){
	for(int i = 2;i <= N/2;i++){
		if(!vis[i])prime[k++] = i;
		for(int j = 0;j < k&&prime[j]*i<=N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
// 埃筛
int vim[N];
void Ai_init(){
	for(int i = 2;i <= N;i++){
		if(!vim[i]){
			int l = 2;
			while(l*i<=N){
				vim[l*i] = 1;
				l++;
			}
		}
	}
}
void solve(){
	Ou_init();
	Ai_init();
	for(int i = 2;i <= N;i++){
		if(vis[i]!=vim[i])cout<>t;
	// while(t--)
	solve();
	return 0;
}

简单记录一下板子
快读

template 
inline void read(T &res)
{
	char c;
	T flag = 1;
	while ((c = getchar()) < '0' || c > '9')
		if (c == '-')
			flag = -1;
	res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	res *= flag;
}