C++ 寻找小于给定整数的最大质数

对于给定的 n，求比 n 小的质数中最大的一个。

质数是指一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数。

**时间限制：**1000 **内存限制：**65536

输入一个整数 n。（ 2 < n < 10000）

输出一个整数，即题目要求的解。

样例输入 100

样例输出 97

C++ 代码：

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    for (int i = n - 1; i >= 2; i--) {
        if (isPrime(i)) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

解题思路： 从 n-1 开始依次判断每个数是否为质数，如果是则输出该数并结束程序。判断质数的方法是，从 2 开始依次判断能否整除该数，如果能则不是质数，否则是质数。时间复杂度为 O(n * sqrt(n))。