题解 | 筛法判断质数

#include<bits/stdc++.h>
using namespace std;
bool isprime (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 t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n;
        cin>>n;
        if(isprime(n)) cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }
}

思路很简单，就是遍历找有没有余数为零的有则false否则true

时间复杂度优化：n/i避免遍历重复的数。