纯暴力（时间复杂度为O(n)，容易TLE）

#include <iostream>
#include <cstdio>
using namespace std;
bool check(int n)
{
    if (n<2) return false;
    for (int i=2;i<n;i++)
    {
        if (n%i==0) return false;
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    while (n--)
    {
        int a;
        cin>>a;
        if (check(a)) puts("Yes");
        else puts("No");
    }
    return 0;
}

优化之后，妥妥的O(根号n)

质数的重要性质：一个数d整除n，即d|n，则n除以d同样整除n，即(n/d)|n。
因此，枚举因子的时候，就不必i<=n，而是优化成i<=n/i即可，这样时间复杂度降为了根号n
注意：1、不建议写成i*i<=n,这样容易溢出或者爆int
      2、不建议写成i<=sqrt(n)，每次调用这个数学函数，会很慢

#include <iostream>
#include <cstdio>
using namespace std;
bool check(int n)
{
    if (n<2) return false;
    for (int i=2;i<=n/i;i++)
    {
        if (n%i==0) return false;
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    while (n--)
    {
        int a;
        cin>>a;
        if (check(a)) puts("Yes");
        else puts("No");
    }
    return 0;
}