题意整理。

• 输入一个大于1的数。
• 判断这个数是否是质数。

方法一（循环）

1.解题思路

• 如果一个数除了被1和它本身整除，不能被其它任何数整除，则这个数是质数。所以只需要验证输入的数字n能否被2到n-1之间的任何数整除。
• 再进一步思考，如果n能被一个大于$\sqrt{n}\backslash sqrt\{n\}$的数整除，我们不妨设这个大于$\sqrt{n}\backslash sqrt\{n\}$的数为t，则n也一定能被$n\mathrm{/}tn/t$整除，而n/t是小于$\sqrt{n}\backslash sqrt\{n\}$的，所以只需验证输入的数字n能否被2到$\sqrt{n}\backslash sqrt\{n\}$之间的任何数整除。

动图展示：

2.代码实现

#include <iostream>
using namespace std;

//判断是否是质数
bool isPrime(int x){
    for(int i=2;i*i<=x;i++){
        //如果一个数能被2到根号x之间的任意一个数整除，则不是质数
        if(x%i==0){
            return false;
        }
    }
    return true;
}

int main() {

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

    return 0;
}

3.复杂度分析

• 时间复杂度：假设输入的数是n，循环最多执行$\sqrt{n}-1\backslash sqrt\{n\}-1$次，所以时间复杂度为$O(\sqrt{n})O(\backslash sqrt\{n\})$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。