1129.连续质数和

题解

2021刘裕康3友情提供

题目描述
——————————————————————————————————————————————————————————————————————
质数又称素数，是大于 1 的正整数，除了 1 和它本身外不能被其他自然数整除，有无限 个，比如,2、3、5、7 等都是质数，但比如 9 就不是质数，因为它除了能被 1 和它自己整 除外，还能被 3 整除。
悦悦小朋友对这类质数非常感兴趣，因为他发现有一些数是能通过连续的质数相加得 到的。比如 5+ 7 + 11 + 13 + 17=53，也就是整数 53 可以由连续的质数 5、7、11、13、17 相 加得到。有时相加的方案还不止一种，比如整数 41 就有 3 种不同的连续质数相加方案： 2+3+5+7+11+13=41，11+13+17=41，还有一种就它本身，即 41=41。但也有的数是没有这样 相加方案的，比如整数 20 就找不到连续质数相加的方案，虽然 7 + 13 或者 3 + 5 + 5 + 7 的 结果都是20，但前者没有连续，后者质数被重复相加了 。悦悦在纸上写了 N（1≤N≤100000） 个数，他想知道每一个整数 Mi（2≤Mi≤10000，1≤i≤N）到底有多少种连续质数相加的 方案？请你编程帮助他一下吧。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
输入
——————————————————————————————————————————————————————————————————————
输入从文件中读取，输入共 N+1 行。 第 1 行一个整数 N，表示悦悦在纸上写了 N 个整数。
接下来每行一个整数，其中第 i+1 行表示整数 Mi。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

输出
——————————————————————————————————————————————————————————————————————
结果输出到文件中，输出共 N 行。
输出的第 i 行表示整数 Mi 有多少种连续质数相加的方案。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

样例输入
——————————————————————————————————————————————————————————————————————
4
2
12
17
20
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

样例输出
——————————————————————————————————————————————————————————————————————
1
1
2
0
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

数据范围限制
——————————————————————————————————————————————————————————————————————
对于 30%的数据保证 1≤N≤100，2≤Mi≤100。
对于 50%的数据保证 1≤N≤1000，2≤Mi≤1000。
对于 100%的数据保证 1≤N≤100000，2≤Mi≤10000。

提示
——————————————————————————————————————————————————————————————————————
样例中悦悦写了 4 个整数，分别为 2，12，17 和 20。
因为 2=2，所以 2 可以找到满足条件的 1 种方案。
因为 5+7=12，所以 12 有 1 种方案。
因为 2+3+5+7=17，17=17，所以 17 有 2 种方案满足条件。
20 没有满足条件的方案，所以输出 0。

原思路

表格化，首先把1到10000所有数可以用多少种质数和表示记录下来，
然后再查询，可以用f[i]存储，
设要查第x个数，直接输出f[x],重点在于如何求出f[i]里的值，
我们可以先筛出1到10000中的所有质数，
然后求出前缀和，用sum[i]表示，
设i,j以及s(s代表质数数组的长度),由i一直循环到s,里面再套一层循环，j=1;j<i;j++。
然后sum[i]-sum[j]的值代表这个数可以用素数合表示，
即f[sum[i]-sum[j]]++,前提为sum[i]-sum[j]的值要小于10000，因为x<=10000。

简化思路

记录1~10000中所有素数booki，求出前缀和sumi，储存好每个数的出现次数fi，输入x，输出f x

想看代码？
提示：文中有超链接