中山大学移动信息工程学院本科生实验报告（2015学年春季学期）课程名称：Algorithm design 任课教师：实验1 1259. Sum of Consecutive Primes1.实验题目ConstraintsTime Limit: 1 secs, Memory Limit: 32 MBDescriptionSome positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive primenumbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.Your mission is to write a program that reports the number of representations for the given positive integer.InputThe input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.OutputThe output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.Sample Input231741206661253Sample Output1123122.实验目的掌握快速打印素数表的方法，比如素数筛法，以及对素数筛法进行优化。
3.程序设计解题思路：先打印10000以内的素数表。
对每个输入值，枚举连续的素数的起点，寻找是否有一段连续的素数与它相等，如果有则累加答案。
求素数算法原理：打印素数是一个比较基础的问题，掌握求素数的方法因而也是一项基本功。
（1）暴力：如果题目只需要判断少量数字是否为素数，可以直接枚举因子2...sqrt(N)，检验是否整除N；只需要枚举到sqrt(N)的原因很直观，如果N在<sqrt(N)的范围找不到一个因子，则在> sqrt(N)也必然找不到，所以只有1和自身两个因子，故为素数。
时间复杂度：O(n*log(n))。
（2）排除法：根据课堂上的学习，我们知道算法如果写成线性算法，也就是O(n)，已经算是不错了，但是最好的是O(Log(n))的算法，这是一个对数级的算法，二分取中（Binary Search）正是O(Log(n))的算法。
通常来说，O(Log(n))的算法都是以排除法做为手段的。
所以，找质数的算法完全可以采用排除法的方式。
如下所示，这种算法的复杂度是O(n(log(logn)))。
但是一般题目中要用到判断素数和求素数，数据规模也比较大的话，一般不用这种直接求法。
实际中的算法是，我把质数事先就计算好，放在一个文件中，然后在程序启动时（注意是在启动时读这个文件，而不是运行时每调用一次就读一次文件），读取这个文件，然后打印出来就可以了。
如果需要查找的化，二分查找或是hash表查找将会获得巨大的性能提升。
当然，这样的方法对于空间来说比前面两个都要消耗得大，但是你可以有O(log(n))或是O(1)的时间复杂度。
参考一些打印素数的方法：/articles/3738.html正则表达式检查素数（好像很NB的样子）：/articles/2704.html /archives/algebra-with-regexes（3）素数筛法：任何合数都能表示成一系列素数的积。
一般的素数筛法：初始时，假设全部都是素数，当找到一个素数时，这个素数乘上另外一个数之后都是合数，把这些合数都筛掉（标记）。
这种算法缺点：会造成重复筛除合数，影响效率。
比如10，在i=2的时候，k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次。
所以，也就有了快速线性筛法。
快速线性筛法：不重复筛选（但是算法的时间复杂度不是O(n)）快速线性素数筛法在这次的几道题目中都用到。
这部分的素数打印方法在后面的题目都有用到，比较重要，这里贴上完整代码：4.程序运行与测试样本输入样本输出5.实验总结与心得掌握了快速线性素数筛法。
实验2 1231. The Embarrassed Cryptography 1.实验题目ConstraintsTime Limit: 2 secs, Memory Limit: 32 MBDescriptionThe young and very promising cryptographer Odd Even has implemented the security module of a large system with thousands of users, which is now in use in his company. The cryptographic keys are created from the product of two primes, and are believed to be secure because there is no known method for factoring such a product effectively.What Odd Even did not think of, was that both factors in a key should be large, not just their product. It is now possible that some of the users of the system have weak keys. In a desperate attempt not to be fired, Odd Even secretly goes through all the users keys, to check if they are strong enough. He uses his very poweful Atari, and is especially careful when checking his boss' key.InputThe input consists of no more than 20 test cases. Each test case is a line with the integers 4 <= K <= 10100 and 2 <= L <= 106. K is the key itself, a product of two primes. L is the wanted minimum size of the factors in the key. The input set is terminated by a case where K = 0 and L = 0.OutputFor each number K, if one of its factors are strictly less than the required L, your program should output "BAD p", where p is the smallest factor in K. Otherwise, it should output "GOOD". Cases should be separated by a line-break.Sample Input143 10143 20667 20667 302573 302573 400 0Sample OutputGOODBAD 11GOODBAD 23GOODBAD 312.实验目的通过分析简化题目用意，提出解决问题的模型，比如在这道题目中，用9进制转换为10进制数即可。
3.程序设计解题思路：先预处理不超过10^6 的所有素数。
（筛法）对每个不超过L的素数，检查是否能整除K。
高精度运算。
(除法？快速取模？)数据规模大，有必要压缩（转换为大进制数，如1000进制）。
算法原理：高精度取余：这道题用简单的快速线性素数筛法+高精度取余就能过，但是TA提到可以使用一些改善高精度运算的效率的方法。
在网上查了一些文章，提到改善高精度运算的效率的方法: 扩大进制数。
理论上来说,高精度运算所用的数组中的每个数表示的数字越多,数组的长度就越小,程序运行的时间也就越短,但是,我们还需要考虑到计算机中的一个数的取值范围,必须保证它们在运算过程中不会越界。
比如扩大为1000进制数则如下：相对应的取余函数也要改变：4.程序运行与测试（1）快速线性素数筛+直接高精度除法，TLE检查后发现素数筛法忽略了偶数的标记。
虽然发现最后过不了的原因和这个无关。
这种就是没有标记素数2的倍数的。
改正：这个细节在这道题虽然不会影响结果，但是在其他的一些题目很可能就是一个很难察觉的BUG，所以写代码的时候还是要尽量使得代码健壮些。