问题 D: 多少种方法

问题 D: 多少种方法

时间限制: 1 Sec  内存限制: 128 MB
提交: 106  解决: 50
[状态] [讨论版] [提交] [命题人:]
题目描述

听说大一的小伙伴们刷题特别crazy,LM大魔王也有点按耐不住了,也开始刷题啊。于是他找了下面一道题开始做,但这道题好难啊,听说LM大魔王用了好久好久好久好久好久。。。的时间才做出来。题目如下: 一些正整数都可以被连续的一个或多个素数之和表示。例如,整数53有两种表示5 + 7 + 11 + 13 + 17和53。41有三种表示2 + 3 + 5 + 7 + 11 + 13、11 + 13 + 17和41。3只有一种表示3。整数20没有这样表示。注意,被加数必须为连续的素数,所以整数20不可以表示为7+13也不可表示为3+5+5+7。  你的任务是编写一个程序,计算出给定的正整数能有多少连续素数之和表示方法。 Crazy and clever的小伙伴们你们能用多长时间A掉呢?

输入

有多组输入。每行输入一个正整数N(2<=N<=10000).

输出

对应每组输入的数据N,输出有多少种连续素数之和表示N的方法。

样例输入 Copy
2
3
17
41
20
666
12
53
样例输出 Copy
1
1
2
3
0
0
1
2