Acwing 866. determining prime numbers by trial division

Given n A positive integer ai, Determine whether each number is a prime number .

Input format
The first line contains integers n.

Next n That's ok , Each line contains a positive integer ai.

Output format
common n That's ok , Among them the first i Line output the i A positive integer ai Is it a prime number , Yes, output Yes, Otherwise output No.

Data range
1≤n≤100,
1≤ai≤2³¹−1

sample input ：
2
2
6
sample output ：
Yes
No

Method 1: Direct violence enumeration O(n²)
But higher requirements will lead to overtime

bool is_prime(int n)
{
    
    if(n < 2) return false;
    for(int i=2; i <= n; i++)    
        if(n % i == 0)
            return false;
    return true;
}

Optimization idea ： You only need to traverse half
because d|n when , n/d|n It's OK ; among d Representation factor ,n It means a number , | To divide or divide
Put it in order ： d <= n/d that will do ; have to d * d <= n that will do ,
so , When looking for factors , Just traverse the root n Part can be

Method 2： Use it directly sqrt function

bool is_prime(int n){
    
    if(n < 2) return false; //2 Is the smallest prime number , If n Less than 2, that n It must not be a prime number 
    for(int i = 2;i <= sqrt(n);i ++){
     // Optimization part 
        if(n % i == 0){
      // If it can be i to be divisible by , This number is not prime 
            return false;  // Return no 
        }
    }
    return true; // Return is 
}

however , This sqrt The bottom layer of the function runs very slowly , Every time this line of code is executed , Need to calculate once , Let's look at other methods

Method 3：
Optimize the traversal code to for(int i = 2;i * i <= n;i ++), Basically, it is similar to the above , But there may be a risk of overflow , Not recommended

Method 4：
Optimize the traversal code to for(int i=2; i <= n / i; i++), The principle is the same as above , But there is no risk of data overflow , This is recommended

Recommended method complete code

#include <iostream>

using namespace std;

//  Trial division 
//  take O(n)  Down to  O(sqrt(n))
bool is_prime(int n)
{
    
    if(n < 2) return false;
    // for(int i=2; i * i <= n; i++) //  There may be spillover risk 
    // for(int i=2; i <= sqrt(n); i++) // sqrt  Every time the function calculates , Affect efficiency 
    for(int i=2; i <= n / i; i++)   //  Just judge the smaller divisor of the two 
        if(n % i == 0)
            return false;
    return true;
}

int main()
{
    
    int m;
    cin >> m;
    while(m --)
    {
    
        int c;
        cin >> c;
        if(is_prime(c)) puts("Yes");
        else puts("No");
    }
    return 0;
}