AcWing 866 试除法判定质数_acwing 866. 试除法判定质数

题目描述：

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

输入格式

第一行包含整数n。接下来n行，每行包含一个正整数ai。

输出格式

共n行，其中第 i 行输出第 i 个正整数ai是否为质数，是则输出“Yes”，否则输出“No”。

数据范围

1≤n≤100, 1≤ai≤2∗10^9

输入样例：

2
2
6

输出样例：

Yes
No

分析：

质数的判定是数论中最基础的质数。首先，1既不是质数也不是合数，只能被1和自身整除的整数称为质数。所以一般采用试除法来判断质数，常规的是从2到n枚举除数，一旦n能被i整除，说明n不是质数。这种办法的时间复杂度为O（n），而且往往需要特判n为2的情形。

不妨先回忆下整除的定义：若整数b除以非零整数a，商为整数，且余数 为零， 我们就说b能被a整除（或说a能整除b），b为被除数，a为除数，即a|b（“|”是整除符号），读作“a整除b”或“b能被a整除”。a叫做b的约数（或因数），b叫做a的倍数。

由i | n,可以推出 (n / i) | n，所以如果n有个约数是小于根号n的，那么必定存在另一个约数大于根号n，反之，试除法过程中除到根号n了还没有找到n的因子，说明大于根号n的数也不会有n的因子，故可以只枚举根号n个数，时间复杂度也是根号n。

循环的写法：for(int i = 2;i <= n / i;i++)。下面说下其它几种写法的缺点，for(int i = 2;i <= sqrt(n);i++)，每次循环都要执行sqrt函数，效率低，当然可以先令t = sqrt(n),循环时i不超过t即可。另一种写法是for(int i = 2;i * i <= n;i++)这种情况当n足够大时，乘法运算可能发生溢出。所以一般写出i <= n / i的形式或者先求出sqrt(n)。

#include <iostream>
using namespace std;
bool isprime(int n){
    if(n == 1)  return false;
    for(int i = 2;i <= n / i;i++){
        if(!(n % i))    return false;
    }
    return true;
}
int main(){
    int n,x;
    cin>>n;
    while(n--){
        cin>>x;
        if(isprime(x))  cout<<"Yes"<<endl;
        else    cout<<"No"<<endl;
    }
    return 0;
}