引用:
作者: polyrandom  我没想出O(I*K)的算法，我想出的就是最简单的brute force，所以连复杂度都懒得去算了。 |
brute force 也就 O(2^k * k) 的复杂度，考虑到 I 和 k 的关系，其实快的有限。这个算法的基本思路是：
1. 记
是能够所有能够被分解为前 m 个质数中某些数之和且小于 I 的数构成的集合。
2. 则
)
，这里
是第 m+1 个质数，
是
中每个元素加上
后得到的集合。
3. 从
开始算到
，最后检查一遍就好了。
这个过程中任意一个
，大小不超过 I ，很容易做到计算每个
的时候复杂度是 O(I) ，一共计算 k 个，所以复杂度是 O(I*k)。