第 K 个最小的素数分数
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。

对于每对满足 0 < i < j < a r r . l e n g t h 0 < i < j < arr.length 0<i<j<arr.length的 i i i 和 j j j ，可以得到分数 a r r [ i ] a r r [ j ] \frac {arr[i] }{ arr[j]} arr[j]arr[i]​ 。

那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 a n s w e r [ 0 ] = = a r r [ i ] answer[0] == arr[i] answer[0]==arr[i] 且 a n s w e r [ 1 ] = = a r r [ j ] answer[1] == arr[j] answer[1]==arr[j] 。

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]

解释：已构造好的分数,排序后如下所示:

1/5, 1/3, 2/5, 1/2, 3/5, 2/3

很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

提示：

2 < = a r r . l e n g t h < = 1000 2 <= arr.length <= 1000 2<=arr.length<=1000
1 < = a r r [ i ] < = 3 ∗ 104 1 <= arr[i] <= 3 * 104 1<=arr[i]<=3∗104
a r r [ 0 ] = = 1 arr[0] == 1 arr[0]==1
a r r [ i ] arr[i] arr[i] 是一个 素数 ， i > 0 i > 0 i>0
arr 中的所有数字 互不相同 ，且按 严格递增 排序
1 < = k < = a r r . l e n g t h ∗ ( a r r . l e n g t h − 1 ) 2 1 <= k <= \frac {arr.length *(arr.length - 1) }{2} 1<=k<=2arr.length∗(arr.length−1)​

class Solution {
   

public:

    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
   
        vector<pair<int, int>> a;
        for (int i = 0; i < arr.size(); ++i) {
   
            for (int j = i + 1; j < arr.size(); ++j) {
   
                a.push_back({
   arr[i], arr[j]});
            }
        }
         sort(a.begin(), a.end(), [](const auto& x, const auto& y) {
   
            return x.first * y.second < x.second * y.first;
        });
        return {
   a[k - 1].first, a[k - 1].second};
    }
};