给你两个整数 n 和 s。
考虑所有小于等于 n 的 质数 。从这些质数中选择一个 子集 ,并满足以下条件:
s 的前提下,使总和 尽可能大。返回一个包含所选质数的整数数组,并按 递增 顺序排列。如果不存在合法的 非空 子集,则返回空数组。
质数 是大于 1 且只有 1 和它本身两个因数的自然数。
子集 是从一个集合中选择零个或多个不同元素得到的集合。
如果数组 a 和数组 b 在第一个不同的位置上,a 中的元素更小,则称 a 的 字典序更小。如果在较短数组的长度范围内所有元素都相同,则较短的数组字典序更小。
示例 1:
输入: n = 7, s = 20
输出: [2, 3, 5, 7]
解释:
n = 7 的质数为 2、3、5 和 7。2 + 3 + 5 + 7 = 17,小于等于 s = 20。[2, 3, 5, 7]。示例 2:
输入: n = 15, s = 18
输出: [5,13]
解释:
[5, 13]、[7, 11]、[2, 3, 13] 和 [2, 5, 11]。由于该总和恰好等于 s,因此 18 是可能达到的最大总和。[5, 13] 和 [7, 11] 包含的质数最少,均为两个。[5, 13] 的字典序更小,因为它的第一个元素 5 小于 7。因此,答案为 [5, 13]。示例 3:
输入: n = 5, s = 1
输出: []
解释:
s = 1。
提示:
1 <= n <= 10001 <= s <= 1000