线性筛素数（巨好理解）

题目描述

如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）

输入格式

第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。

输出格式

输出包含M行，每行为Yes或No，即依次为每一个询问的结果。

输入输出样例

输入 #1

100 5
2
3
4
91
97

输出 #1

Yes
Yes
No
No
Yes

介绍

素数有很多种筛法，比较多见的是埃式筛法（复杂度是nloglogn）。
这里想讲的是线性筛素数。
首先任何一个数a, 一定由某个 最小素因子b * 另一个数c得来的，即
$a=b（最小素因子）\ast c(c>=b)$a=b（最小素因子）∗c(c>=b)
用 $xiao\left[i\right]$xiao[i] 表示 $i$i 的最小素因子
我们枚举c，假设我们已经得到了小于c的所有素数 $p\left[j\right](1\le j\le cnt)(cnt为小于c的素数总数）$p[j](1≤j≤cnt)(cnt为小于c的素数总数）
令 $t=c\ast p\left[j\right]$t=c∗p[j]，那么我们就可以更新 $xiao\left[t\right]=p\left[j\right]$xiao[t]=p[j]了。
这样一来，每个数 $i$i 的 $xiao\left[i\right]$xiao[i] 只会被更新到一次，复杂度就是O(n)
至于 $p\left[j\right]$p[j]怎么得到，我们在枚举c的时候，如果 $xiao\left[c\right]=c$xiao[c]=c，即最小素因子为本身，那么这个数就是一个素数，我们直接 $p[++cnt]=c$p[++cnt]=c即可。
代码很是简短，建议结合代码理解。

下面贴代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 10000005
#define inf 2147483647
using namespace std;
int x[N], p[N], cnt;
int main(){
	int i, j, t, n, m;
	scanf("%d%d", &n, &m);
	for(i = 2; i <= n; i++){
		if(!x[i]) x[i] = p[++cnt] = i;
		for(j = 1; j <= cnt; j++){
			t = i * p[j];
			if(t > n) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
		}
	}
	for(i = 1; i <= m; i++){
		scanf("%d", &j);
		if(x[j] == j) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}