【例36.3】 最大质数

解题思路

从n向下检查质数，找到第一个即输出。判质数时试除到平方根；n<2直接No。

正确性说明

按上述推导执行：每次仅处理当前输入或当前步骤，并把它对答案的贡献计入对应状态。所有需要处理的情况均被覆盖，结束时保存的量就是题目所求。

易错点

1不是质数；遇到首个质数后结束，不继续输出更小质数。

复杂度

若检查k个候选，时间O(k√n)，最坏界O(n√n)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    for (long long x = n; x >= 2; x--) {
        bool prime = true;
        for (long long d = 2; d <= x / d; d++)
            if (x % d == 0) {
                prime = false;
                break;
            }
        if (prime) {
            cout << x << "\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}