AcWing 866. 试除法判定质数

AcWing 866. 试除法判定质数

参考题目：AcWing 866. 试除法判定质数

因数：整数a除以整数b(b≠0) 的商正好是整数而没有余数，我们就说b是a的因数。ps:如果d|n，那么(n / d)|n，所以在枚举的时候只需要枚举较小的质因子即保证d < (n / d)质数：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。(规定：1既不是合数也不是质数) 代码：

时间复杂度： O ( n n ) O(n sqrt n) O(nn ​)

#include 
#include 
#include 

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false; // 如果小于2一定不是质数
    for (int i = 2; i <= x / i; i ++ ) //只需要枚举较小的质因子
        if (x % i == 0) return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    
    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}

参考资料：
https://www.acwing.com/activity/content/code/content/49970/