题目描述

试除法判定质数

暴力做法：直接以2作为除数开始求余数

当除数为从2~n时，时间复杂度为O(n)

实际上被除数有约数则必然成对出现，则时间复杂度可以变为O(√n);

C++ 代码

#include<iostream>
using namespace std;
int n;
bool is_prime(int x)        //判断x是否为质数
{
    if(x<2)return false;          //质数都大于2

    //当除数从i~n时时间复杂度为O(n)
    //除数是大小两个成对出现，所以只需要除以其中较小的一个即可，此时时间复杂度为O(√n)
    for(int i=2;i<=x/i;i++)      //1.i<=sqrt(x),则每循环一次都要调用一次sqrt函数
                                 //2.i*i<=x,则数值太大后可能会溢出
    {
        if(x%i==0)return false;
    }
    return true;
}
int main()
{
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        if(is_prime(x))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}