C++判断一个数是不是质数_c++判断质数

详见及参考：
https://www.nowcoder.com/practice/b8bb5e7703da4a83ac7754c0f3d45a82?tpId=225&tags=&title=&difficulty=0&judgeStatus=0&rp=0

质数是只能被1及其本身整除的正整数。例如2是质数：2÷1=2，2÷2=1，即2被1整除是2，2被其本身整除是1。2只能被1及其本身整除，因此它是质数。

判断一个数n是不是质数，

• 1.首先，任何正整数都能被1及其本身n整除，因此将循环范围定在2到 n-1之间。
• 2.再进一步思考，如果$n$能被一个大于$\sqrt{n}$的数整除，
  我们不妨设这个大于$\sqrt{n}$的数为$t$，则$n$也一定能被$n/t$整除，而$n/t$是小于$\sqrt{n}$的，所以只需验证输入的数字$n$能否被$2$ 到$\sqrt{n}$之间的任何数整除。
  举个例子：
  例如$n=21$,$21$能被一个大于$\sqrt{21}$的$7$即$\sqrt{49}$整除($21÷7=3$),则反过来$21$也能被小于$\sqrt{21}$的3即$\sqrt{9}$整除。
  因此我们只需要验证输入的数字$21$能否被$2$到$\sqrt{21} $之间的任何数整除即可。

#include <iostream>
using namespace std;

bool isPrime(int x){
    for(int i=2; i*i<=x; i++){
        if (x % i == 0)
            return false;
    }
    return true;
}


int main() {

    int num;
    cin >> num;
    
    if (isPrime(num)){
        cout << "是质数" <<endl;
    }
    else
        cout << "不是质数" <<endl;

    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

#include <iostream>
using namespace std;

int main() {

    int num;
    cin >> num;

    bool flag = true; // 必须先初始化flag。若直接bool flag;会报错。
    for (int i=2; i*i<=num; i++){ //遍历到根号num就可以了
        if (num % i == 0) { //可以整除，说明num不是质数
            flag = false;
            break;
        }
    }

    if (flag)
        cout << "是质数" <<endl;
    else
        cout << "不是质数" <<endl;

    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