寻找大素数
人总是有寻找资源的原动力
QQ 群是寻找信息资源的一个重要渠道。优质的专业社群，专业技术问题的探讨、信息共享，给与个体的帮助非常大。日常的闲聊也能让人获得很多乐趣。
昨天在加一个群的时候，它设置了一个有趣的入群问题：
小于899808659的最大质数是？
低头做事
第一感觉是简单，应该能很快做出来，但随后也感觉这个数稍微有点大，会不会没自己想想的这么简单，也想到了三种可能能解决这个问题的方案：试除法（复杂度约为n^1.5）、欧拉筛法
和
Miller–Rabin素性检测，前两种解决方案以前都写过对应的C代码,第三种也就是知道名字能做什么而已。决定试一把前两种解决方案，感觉以前写过怎也能做出来。前两种选哪一种呢？我也说不太清楚，带着复杂的的心情写完了第一个方案的程序，
在写程序的时候发现 899808659
本身就是一个素数，可惜题目要的是比这个数略小的。程序运行了10多分钟发现程序还在跑。感觉糟了要是要找的这个数和这个数差的范围太大怎么办?。然后直接放弃了想着写欧拉筛法吧，屋漏偏逢连阴雨，欧拉筛法忘记怎么写了，当时理解的不是很深刻的判断终止循环地方果然又记不起来原因了。琢磨半天搞明白后，开始写代码，写的时候发现分配数组太多，分配不了，在ruby下数组的大小也就能分配5亿个，在C语言中也是大概这么多个int类型的数组。但这个算法能在线性时间内筛除区间内的所有素数，感觉很有意思、神奇、实用，自己也快忘记具体细节了，就决定花点时间复习一下，顺带用ruby写了一个版本。显然最终还是没能解决最终的问题。
怎么办呢？怎么办呢？怎么办呢？
检索了一下，看了几篇文章，发现大素数及其判定问题原来是个国际性的难题。大素数的一个重要应用在RSA加密中。虽然899808659这个素数虽然不小了，但还是挺小的，也有一些ACMer公布了一些判断2^63内数的素性测试的现成程序，但战胜失败的强烈欲望我感觉非得写个程序搞定不可，不然太没面子了。然后开始跳入了一个深坑。参考
大素数判断和素因子分解（miller-rabin，Pollard_rho算法）
这篇blog，一开始怎么也不找头脑，想放弃，但是感觉放弃可不行啊，遇到困难就放弃怎么能学到东西呢？硬着头皮往前上，发现有段代码不懂，不知怎么脑洞突然大开，直接搜索这段代码，进入Miller-Rabin素数测试学习笔记这篇blog发现原来不理解的代码其实是二次探测定理的使用。总结起来这个理解算法的难点就可以归结为
理解代码中溢出的解决，二次探测定理，费马小定理等这些技术和原理。现在就等二次探测定理
归位，开工检索，检索到Matrix67先前有篇blog 数论部分第一节：素数与素性测试里面有这个关键词。Matrix67是第一个让我深刻体会到blog还能这么有意思,细细品读，醍醐灌顶，这篇文章果然有没有失望，深入浅出，又是一片好文。折腾到晚上程序写完了。程序连接
程序输出来好多结果，感觉数字8一直没变，坏了，数据太多了。把2改大后结果一下就出来了
899808619验证不过去，额，眼前一黑，Miller–Rabin那么低的概率判断失误的情况居然碰上了。
反正离899808659挺近的，就枚举一下（899808619，899808659）区间的数吧，实在折腾的够呛了，最后真正的结果是下面这个数，也就这一个。
899808641抬头看路
反思整个过程，自己曝露出很多缺点。
有句话说心中有数，手上不乱。看到问题没有好好的分析问题，有什么解决方案，有多少，分析每个方案的特点、所能解决的问题。上来就凭感觉做，然后想大力出奇迹，简直是痴人说梦，事倍功半，过程中老感觉不踏实，那里怪怪的。那每种方案的复杂度是多少呢，能解决的问题能力多大呢？试除法的时间复杂度我起初一直错误的以为是 \(O(n^{1.5})\),实际应该为 \(O(n^{0.5})\)，那其实是遍历区间内所有素数筛法的时间复杂度，而\(O(n^{0.5})\) 才是 筛选一个数的时间复杂度。虽然感觉也怪怪的，但是没有细心的想想为什么感觉怪怪的。错误的时间复杂度估计，粗心大意，也是过于快放弃这种方案的原因。有句话还是挺有道理的，对感觉奇怪的地方进行深入的思考，查找资料求证，就可能会发现一些令人吃惊的与设想不同的结果。
其次，调试程序大意，主观臆断。代码没进行单元测试，试除法程序运行时间过长，没有具体分析原因就直接尝试第二种方案。
第三，偏离主目标，这是严重的路线方向问题。明显发现欧拉筛法行不通的时候，仍花费不少时间在上面，这个事情应该放到延迟重要的事情。
总结
对于这个事情的结果是，一个一小时内可以解决的问题终于在几个小时候后把问题解决了。顺利的进入了群，自豪骄傲。
