算法

(暴力枚举) $O(\sqrt{n})$

试除法。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define fs(i,x,y,z) for(int i=x;i<=y;i+=z)
int n,a;
bool prm(int k){
    if(k<2) return 0;
    if(k==2||k==3||k==5) return 1;
    for(int i=2;i<=sqrt(k)+1;i++) if(k%i==0) return 0;
    return 1;
}
int main(){
    cin>>n;
    fs(i,1,n,1){
        cin>>a;
        if(prm(a)) cout<<"Yes\n";
        else cout<<"No\n";
    }
}