一日一蛋疼之素数验证
随便给你一个数字N，怎么验证是不是素数？
最快速且最蛋疼的方法是建立一个素数索引PRIME,然后PRIME[N]就知道此数是不是素数了，时间直接就是神奇O(1)
当然此神奇算法的必要条件就是先建立了一个大小至少为N的数组PRIME，然后用漏斗法除掉合数(Of Course 如果你觉得时间够多且用不掉，也可以直接一个一个的验证以剔除合数)
漏斗法的实现就很想一个漏斗了，步骤如下：
1.将数组PRIME清0
2.当然PRIME[1]可以不考虑了
3.步长为2,从PRIME[2]开始，依次取下标4，6，8…2×[N/2] 置1 (事实上如果运气够好 N是2的倍数 经过N/2次操作就可以停止了)
4.步长为3,从PRIME[3]开始，依次取下标6，9，12…3×[N/3] 置1
5.继续去PRIME[I]不为1且有最小的I，依次取下标2I,3I….I×[N/I] 置1
6.重复5直到I>SQRT(N)
我们就得到了一个巨大的素数库，然后碰到一个巨大数字时候，直接看看PRIME[N]是不是0就好，但是会发现在N相当大的时候没有一台超级电脑那会相当的蛋疼
不过这个还是有用的，尤其是破解密码的时候，维护一个巨大的素数库很有必要，尤其对于破解RSA加密，不过一般人是没有这么蛋疼的
针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155(512 bits)被成功分解，花了五个月时间（约8000 MIPS 年）和224 CPU hours 在一台有3.2G中央内存的Cray C916计算机上完成 。
期间有无数次判断因数是否质数，这时候有个表就会很方便了吧
接下来就是传统方法了,大意如下：
给一个循环,从i=2开始 一直到i>SQRT(N)停止
不断用N去除i,如果其中得到余数为0,恭喜你了,N是合数(此处直接%就好了)
如果一直不为0，可以激动了，N是质数
可惜我们已经进行了SQRT(N)次模运算
时间复杂度就是O(SQRT(N))，已经比较高效了，但是还能不能再加速呢？
今天果断看了一个新方法，虽然也很蛋疼
首先要引用 费马小定理 以及 加法定理
费马小定理可以看百度百科的介绍，不过这里就列出来吧
对于一个素数P，取任意A＜P，有A^(P-1)≡1(mod P)
加法定理好像没找到说明，列出来吧
对于一个质数P,若X^2≡1(mod P),则X≡±1(mod P)
定理的证明过程就略了，有兴趣可以自己试试～书上的证明我愣是看了半小时才发现是印刷错误。。。
现在我们就可以来开始验证素数的过程了～
步骤如下：
1.取[2,N-2]之间任意数字A
2.开始求A^N mod P 的值
3.若N为0，直接返回1，表示到头了
4.求出A^[N/2] mod P的值X 注意 这是一个递归过程 新建一个N=[N/2]并进入第2步
5.Y=X^2 mod P
6.如果Y=1 且 X不等于1或N-1 显然不符合加法定理 于是返回0 表示为合数
7.如果N为基数，第4步时候显然漏乘一个A,乘之 Y = Y × A mod P
8.返回Y
若最后 返回结果为1 即符合费马小定理 我们可以很高兴的对N说 你TM就是个质数
可惜还是高兴太早了
这个算法非常蛋疼之处在于，由于A是随机取得的(即便是伪随机),事实上存在一部分A可以使我们得到错误的结论，合数会伪装成质数
这个概率是 1/4 也就是说拿100个数字测试 我们会错大概25次
那我们做了这么久又有啥意义？这就是概率问题了，如果我们连续测试多次，比如5次，这样依旧无法测试质数的概率就是将近千分之一 在这个一切都不确定的世界，还是可以接受的，如果你还不爽，可以测20次，概率是1/POW(4,20)，这个概率应该跟平常电脑运算时候出错的概率相当了
时间呢？这个一定高效吗？给定一个数字 大小接近2的9999次方，不要问我为什么会取这种数字，实际工程中遇到的数字应该会比这个还大。。。
此算法很容易看出来时间大概是O(logN),也就是9999，就算验证20次，也就9999×20 = 199980
在看看传统算法 只需要验证一个 但是要计算 9.99e+1504，这个壮观了吧
再来计算蛋疼的给出篇首神奇算法PRIME数组的时间复杂度
可以推出为 N/2 + N/3 + N/5 + N/7 + N/11 + …. + N/I 其中I为小于等于根号N的最大质数
这个没有具体计算 应该是小于2N的 数学不行啊 都忘记了 哪位高手算出来了贴上来吧～
此处之所以不是小于N的值是因为我们没有跳过与之前已筛选数字的公因数
例如筛选3的倍数的时候，6的倍数就被重复访问了，而显然没有必要加上对公倍数的判断
需要的空间，最佳情况,如果PRIME数组是位向量，即每个元素一个比特，我们需要9.98e+3009个比特，即约1.13e+2997 TB的资源
这信息量已经不是蛋疼能偶形容的了
