风灵无畏OI
此站用来记录个人的OI成长史，以后会将个人做的每道题的解题报告发到此站上来，希望大家喜欢！（如有讲得不好的地方请大家指出，我会加以改进。当然也有可能传上来一点乱七八糟的东西）
注：转载文章请标上原址，毕竟码字很辛苦！谢谢！
线性筛
https://www.luogu.org/problem/show?pid=3383
【题目描述】
如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）
【输入格式】
第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。
接下来M行每行包含一个不小于1且不大于N的整数，即询问概数是否为质数。
【输出格式】
输出包含M行，每行为Yes或No，即依次为每一个询问的结果。
【输入样例】
100 5
2
3
4
91
97
【输出样例】
Yes
Yes
No
No
Yes
【说明】
时空限制：500ms 128M
数据规模：
对于30%的数据：N<=10000，M<=10000
对于100%的数据：N<=10000000，M<=100000
样例说明：
N=100，说明接下来的询问数均不大于100且大于1。
所以2、3、97为质数，4、91非质数。
故依次输出Yes、Yes、No、No、Yes。
【题目分析】
此题大家一看到应该就知道，普通的筛法是做不了的，我们只能想想比如线性筛，欧拉线性筛，Miller_Rabin加二次探测什么的（我也不是很懂），于是就用了最简单的线性筛。
【算法讲解】
这里有一位学长讲线性筛的博客：https://liaoy148.lofter.com/post/1da8a74e_b60a4cc
可以去看看他的，讲的很仔细。
我就长话短说吧，我们用p[i]记录当前为止第i个素数。f[i]为true表示i是合数。从2开始枚举。对于每一个数 i ，如果not f[i]，我们就把i扔进p数组。i 就是我们枚举到的这个数字，
i mod p[j]=0的时候我们就弹出这样是不是就保证了， i*p[j]是被它最小的p[j]筛去的
因为一个数字只被最小的质因子筛去只被for一次
所以复杂度是O(n)
【程序代码】
var n,m,i,x,tot:longint;
f:array[0..10000010]of boolean;
p:array[0..10000010]of longint;//数组要开这么大，范围有这么大
procedure prime_table(n:longint);
var i,j:longint;
begin
tot:=0;
f[1]:=true;//这里是需要注意的，当时我就是没注意这里，结果一直wa两个点，后面还是经某何大佬，才A的题。
for i:=2 to n do
begin
if f[i]=false then//表示i为质数
begin inc(tot); p[tot]:=i; end;//把素数按从小到大加入
j:=1;
while i*p[j]<=n do//保证查找的数在1~n范围内
begin
if j>tot then break;//这里是一个小小的优化，
f[i*p[j]]:=true;//表示i*p[j]为合数
if i mod p[j]=0 then break;
inc(j);
end;
end;
end;
begin
readln(n,m);
prime_table(n);//线性筛，把1~n中的素数找出来
for i:=1 to m do
begin
readln(x);
if f[x]=false then writeln('Yes')
else writeln('No');//输出
end;
end.