解题思路

题目要求：从 n 个数里找出第 k 大的数和第 k 小的数，用大的减去小的得到 m，然后判断 m 是不是质数。

怎么找第 k 大和第 k 小？

最简单的方法是把所有数从小到大排好序：

• 第 k 小的数：排序后从左边数第 k 个
• 第 k 大的数：排序后从右边数第 k 个

用 1 开头的下标来算：

• 第 k 小 = a[k]
• 第 k 大 = a[n-k+1]

所以 m = a[n-k+1] - a[k]。

怎么判断质数？

质数是大于等于 2、只能被 1 和它本身整除的数。判断方法：

1. 如果 m 小于 2，直接不是质数
2. 从 2 开始到 根号 m，看有没有能整除 m 的数
3. 如果有，说明不是质数；一个都没有，就是质数

为什么只试到根号 m？ 因为如果一个数有因子，那么至少有一个因子不超过它的平方根。比如 m=36，因子 2 和 18、3 和 12，较小的一半都不超过 6（根号 36）。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a[10005], n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    sort(a + 1, a + 1 + n);  // 从小到大排序

    // 第 k 小 = a[k]，第 k 大 = a[n-k+1]
    int m = a[n - k + 1] - a[k];
    int t = 1;  // 标记 m 是否是质数

    if (m >= 2) {
        // 试除 2 到 sqrt(m)
        for (int i = 2; i * i <= m; i++) {
            if (m % i == 0) {
                t = 0;
                break;
            }
        }
    } else {
        t = 0;
    }

    if (t == 1) cout << "YES" << endl << m;
    else cout << "NO" << endl << m;
    return 0;
}

复杂度分析

• 时间复杂度：O(N log N)，排序的复杂度
• 空间复杂度：O(N)，一个数组存数