【NOIP真题】2002 选数 luogu-P1036 | 适用

洛谷 P1036 这道题，说白了就是从 n 个数里选 k 个，看有多少种组合加起来是素数。

刚上手最容易栽在搜索上。有人习惯用 vis 数组标记，结果把不同顺序当成不同方案，答案直接放大 k! 倍；还有人一上来就对输入去重，其实题目是按位置选数，数值一样但下标不同也算两种。解法很简单：按数组下标严格递增去搜，下一层直接从 i+1 开始，天然不重不漏。

递归边界到了就判断素数。这里别用筛法——最大和能到一亿，开大数组太吃内存。直接用试除法，从 2 枚举到根号 num，绝大多数合数很快就能筛掉。

代码里有几个坑得盯紧。sum 最好当参数传进去，每一层栈帧自带副本，省了回溯时手动减回去的麻烦。is_prime 开头必须加上小于 2 的判断，别忘了 1 不是素数。循环条件写成 i*i<= num，要是误写成 num/2，数据一大铁定超时。