[数据结构与算法]数学知识：试除法判定质数—质数

试除法判断质数C++模板：

bool is_Prime(int x)
{
    if(x<2)return false;
    int mid=sqrt(x);//取出保存，防止每次执行
    for(int i=2;i<=mid;i++)
        if(x%i==0)return false;
    return true;
}

质数： 质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

题目： AcWing 866. 试除法判定质数
给定 n 个正整数 ai，判定每个数是否是质数。

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

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

数据范围
1≤n≤100,
1≤a_i≤2³¹?1

输入样例：

2
2
6

输出样例：

Yes
No

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

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖