C++试除法判定质数_c++如何用试除法判定质数

判断整数n是否是质数：
若n只能被1和n整除，则n为质数，否则不是；

做法：

朴素版：直接枚举2~n-1的每个数，进行判断是能整除n；
优化版：枚举2~sqrt(n) 的每个数，进行判断是能整除n；
1
2

证明（优化版）：

#include<iostream>

using namespace std;

int n;

void judge(int x)
{
    if(x<2) cout<<"No"<<'\n';
    else
    {
        for(int i=2;i<=x/i;i++)//
            if(x%i==0)
            {
                cout<<"No"<<'\n';
                return;
            }
            
        cout<<"Yes"<<'\n';
    }
}

int main()
{
    cin>>n;
    
    while(n--)
    {
        int x;
        cin>>x;
        judge(x);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35