素数筛

当遇到要求 1~n 之间的素数时，最纯的方法是 $n^2$的，稍微聪明点的是 $n√n$的。
遇到 $10^6$或者更大的数据时就挂了。
所以我们需要学习素数筛，可以在接近线性的时间内筛出素数。

这里我只说（会）最好背的一种筛法，复杂度为 $O(nloglogn)$

代码很简洁，四行。
其中 book[i] 表示 i 是否不是素数（book[i] 为 1 时表示 i 不是素数）

for(int i=2;i<=n;i++)
    if(!book[i])
        for(long long j=(long long)i*i;j<=n;j+=i)
            book[j]=1;

那个 j 最好是 long long，不然容易爆。还有 i*i 需要用 long long 进行运算，不然也容易爆。

这个筛（至少）可以过 $10^7$的数据（亲测）。

它运用的思想：

把从 1 开始的、某一范围内的正整数从小到大顺序排列， 1 不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。
——度娘

例题

【模板】线性筛素数 LUOGU – 3383
传送门＝￣ω￣＝

题解：模板题。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m;
bool book[10000005];
int main()
{
    scanf("%d%d",&n,&m),book[1]=1;
    for(int i=2;i<=n;i++)if(!book[i])for(LL j=(LL)i*i;j<=n;j+=i)book[j]=1;
    while(m--){scanf("%d",&n);if(book[n])printf("No\n");else printf("Yes\n");}
    return 0;
}