题目的主要信息：

• 输入一个大于1的数，判断其是否是质数

具体做法：

判断一个数$nn$是否是质数，我们只需要找它有无因子即能否被整除即可。 从2开始遍历到该数前一个数$n-1n-1$，查看每个数能否整除$nn$，如果可以整除即余数为0，则记录下不是质数，跳出循环，输出即可，如果检查完所有的数都没有因子，则它是质数。

其实我们不用遍历到$n-1n-1$，遍历到$\sqrt{n}\backslash sqrt\; n$即可，因为$\sqrt{n}\backslash sqrt\; n$后面如果有因子，必定是乘上另一个小于$\sqrt{n}\backslash sqrt\; n$的数字，那我们前面就已经验证过了，因此以$\sqrt{n}\backslash sqrt\; n$为遍历终点就可以了。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool flag = true;
    for(int i = 2; i * i <= n; i++){ //遍历到根号n就可以了
        if(n % i == 0){ //可以整除，记录不是质数
            flag = false;
            break;
        }
    }
    if(flag)
        cout << "是质数" << endl;
    else
        cout << "不是质数" << endl;
	return 0;
}

复杂度分析：

• 时间复杂度：$O(\sqrt{n})O(\backslash sqrt\; n)$，从2遍历到$\sqrt{n}\backslash sqrt\; n$
• 空间复杂度：$O(1)O(1)$，无额外空间