JavaScript - 有没有一种有效的方法来检查整数“k”是否是素数数组中值的线性组合？

Question

我有一个任意大的整数

k

和任意多个正素数的数组

[p_1, p_2, ..., p_n]

。使用 JavaScript，我想检查

k

是否可以表示为数组值与非负整数系数的线性组合。

但是，我无法找出一种方法来确定任何给定的

k

是否是任何给定数组中的值的线性组合。

此站点上类似问题的唯一答案不起作用，因为我的数组中的所有值都是素数：它们的GCD始终为

1

，余数始终为

0

，并且其返回值答案的表情始终是

True

，即使它应该是

False

。

例如，如果数组具有值

[5, 7, 13]

，则

k = 12

是有效的线性组合 (1×5 + 1×7 + 0×13)，而

k = 16

则不是。

此外，链接的问题和答案中的代码仅检查小于或等于数组值的倍数，并且我希望能够检查比该值大得多的数字。

我想要的可以实现吗？

Answer 1

您可以采用递归方法，获取实际值的增量或检查下一个值。

const
    check = (values, k) => {
        const
            iter = (rest, index) => {
                if (!rest) return true;
                if (rest < 0 || index >= values.length) return false;
                return iter(rest - values[index], index)
                    || iter(rest, index + 1);
            };
    
        return iter(k, 0);
    };

console.log(check([5, 7, 13], 12));
console.log(check([5, 7, 13], 16));