题目描述

给定n个正整数ai，判定每个数是否是质数。

样例

2
2
6

Yes
No

算法

(试除法)

1. 如果x比2小，那么它一定不是质数。因为质数是从2开始的
2. 因为d | n如果成立，那么n/d | n也是成立。二者是成对出现的，所以为了优化算法，枚举到i <= x / i即可，推荐这种写法，比i < sqrt(x)的效率高，比i * i <= x保险，第2种写法如果x很大，搞不好会 溢出，x就成了负数。
3. 如果在2~sqrt(x)之间有x的约数，说明它不是质数，return false即可。
4. 如果遍历完没有，说明是质数，return true即可。

时间复杂度

$O(sqrt(n))$

C++ 代码

#include <iostream>

using namespace std;

bool is_Prime(int x)
{
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i ++)
        if(x % i == 0)
            return false;
    return true;
}

int main()
{
    int n; 
    cin >> n;
    while(n --)
    {
        int a;
        cin >> a;
        if(is_Prime(a)) puts("Yes");
        else puts("No");
    }

    return 0;
}