Antiprime Sequences

【原题链接】

【题意说明】

由n~m这些构成的序列,使用其中任意2~d个连续数的和为合数。并在所有方案在按输出最小序列的那种方案,两数之以“,”分隔;若不存在方案,输出“No anti-prime sequence exists. 

【问题分析】

 本题努力去找非搜索的方法,@_@没找到!最终还是用了dfs。

思路就是很黄很暴力的那种dfs,枚举放第1个数,放第2个数,边放边检查是否满足条件(即包括当前所放的这个数的连续2~d个数的和是否为合数)。若不满足则返回重放!否则继续放下一个数!

注意的地方有:

(1)先把10000以内的合数全部求出来,p[10000]这样的数组标记即可。

(2)连续2~d个数的和是否为合数,是从后往前检查,不满足就退出,利用累加来做。

(3)从第1个数开始,从小到大试,找到了就退出!(记住循环里也要退出!!否则可能会超时!)

原文地址:https://www.cnblogs.com/ahmasoi/p/2764180.html