时间复杂度O（根号n）
d|n 那么 n/d|n 成对出现，只需判断小的那个 d<=n/d 即可

C++ 代码

#include<iostream>

using namespace std;

const int N=105;
int a[N];

bool is_prime(int n)
{
    if(n<2)return false;
    for(int i=2;i<=n/i;i++){//n=2时不会执行这个循环
        if(n%i==0)return false;
    }
    return true;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];

    for(int i=0;i<n;i++){
        if(is_prime(a[i])){
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }

    return 0;
}