这里给出的两份代码都是关于洛谷P3383 【模板】线性筛素数的。两份代码不是一块敲的，码风可能稍有区别。

Eratosthenes筛法

Eratosthenes筛法的核心思想是对于任何一个数，它的整倍数一定不是素数。
时间复杂度：$O(n log log n)$
code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
	register int x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,m,su[10000005];

void make()
{
	int k = sqrt(n + 1);
	for(int i = 2; i <= k; i++)
	{
		if(su[i]) continue;
		for(int j = i * i;j <= n; j = j + i) su[j] = 1;
	}
		
}

int main()
{
	n = read(); m = read();
	make();
	su[1] = 1;
	su[0] = 1;
	for(int i = 1; i <= m; i++)
	{
		n = read();
		printf(su[n] ? "No\n" : "Yes\n");
	}
    return 0;
}

Euler筛法

Euler筛法也叫欧拉筛。
Euler筛法的特点是对于每一个合数，我们只会用它的最小质因数去筛去它，所以Euler筛法的时间复杂度是$O(n)$的。
code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define qwq printf("qwq\n");

using namespace std;

int read()
{
	register int x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,m,x,cnt,vis[10000005],pri[10000005];

void work()
{
	vis[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i]) pri[++cnt] = i;
		for(int j = 1; j <= cnt && i * pri[j] <= n; j++)
		{
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
}

int main()
{
	n = read(); m = read();
	work();
	for(int i = 1; i <= m; i++)
	{
		x = read();
		if(vis[x]) printf("No\n");
		else printf("Yes\n");
	}
    return 0;
}

我们可以看一下这两份代码的运行速度：