复杂度 <nobr> O(nloglogn) </nobr>
证明的话思路是用素数分布定理列出表达式，然后定积分确定时间界（别问我怎么知道的QAQ，万能的知乎），贴个链接赶紧跑orz。
实际上已经很接近 <nobr> O（n） </nobr>了
可以用来筛出某一给定区间的素数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZE=10000010;
int cnt,n,m,prime[SIZE];
bool is_prime[SIZE];
void Eratosthenes()
{
    int tmp=sqrt(n+0.5);
    is_prime[1]=1;
    for(int i=2;i<=tmp;i++)
        if(!is_prime[i])
        {
            prime[++cnt]=i;
            for(int j=i*i;j<=n;j+=i) is_prime[j]=1;
        }
}

int main()
{
    scanf("%d%d",&n,&m);
    Eratosthenes();
    for(int i=1,num;i<=m;i++)
    {
        scanf("%d",&num);
        printf(is_prime[num]==0?"Yes\n":"No\n");            
    }   
    return 0;
}