题目来自于西安葡萄城 2014 年招聘挑战赛
题目8：计算一个尽可能大的素数※
编程语言：不限
题目描述：在有限的时间内，计算出一个尽可能大的素数。
需要随作品提供文档说明算法原理，参考资料等等。
程序说明※
关于「质数」的要求※
程序使用 Miller-Rabin 素性测试算法判断一个 BigInteger 对象是否为质数。既然程序使用的是 Miller-Rabin 算法，那就肯定有 M-R 算法的特点：
Miller-Rabin 算法是一个 RP 算法。RP 是时间复杂度的一种，主要针对判定性问题。一个算法是 RP 算法表明它可以在多项式的时间里完成，对于答案为否定的情形能够准确做出判断，但同时它也有可能把对的判成错的（错误概率不能超过½）。RP 算法是基于随机化的，因此多次运行改算法可以降低错误率。
M-R 算法有\((\frac{1}{4})^K\)的概率错误，本程序默认选取 \(K=4\)，故程序给出的素数中，有 \(0.0390625\) 的概率为合数。当然本程序中 \(K\) 的值是可以修改的，最大值为 111。当 \(K=111\)时，错误率为 \(1.484 \times 10^{-67}\)。
虽然目前有多项式的、确定的、无需其他条件的素性判断算法（AKS 算法）。但这个算法的时间复杂度为\(O(n!)\)，时间复杂度过于高，不适合用于判断大素数。
综上，本次选择 Miller-Rabin 素性测试算法最为合适。
关于「尽可能大」的要求※
为了实现题目「计算出一个尽可能大的素数」中「尽可能大」的要求，我用 C++ 实现了一个 BigInteger 类，最大值为 \(2^{2^{31}-1}=2^{2147483647}\)，最小的数为 \(-2^{2147483647}\)。这是一个很大的数了，举一个直观的例子，科学家估计整个宇宙的原子数量在 \(5.3 \times 10^{80}\) 个。虽然 C\C++ 中有扩展的大整数库/类，但是我想出题者本意应该不是直接使用别人做好的东西来完成，所以才自己造轮子，构造了一个 BigInteger 类。
其核心为 BigInteger 的设计和实现。BigInteger 有以下几个难点：
- 大数乘法
- 大数除法
- 字符串转为大数
- 大数转为字符串
在实现上面的难点时，借鉴了 TAOCP 中的部分算法，Karatsuba 算法和 RSA 加密体系中的部分算法。
关于「有限时间内」的要求※
（入职葡萄城后补充 2014-05-02）
考虑到素数算法很独立，可以利用 MapReduce 的思路，很容易地把待计算的大数集合拆分成并行的多个独立任务各自计算（Map），到达截止时间后汇总出最大值即可（Reduce）。在这里仅谈一下思路：
如何拆分任务※
将自然数中的奇数按照需要的大小分桶即可。
| 并行度（线程数） | 分桶数量 | 桶初始值 | 桶内取下一个数的通项公式 |
|---|---|---|---|
| 1 | 1 | [3] | \(a_{n+1} = a_n + 2\times1\) |
| 2 | 2 | [3, 5] | \(a_{n+1} = a_n + 2\times2\) |
| 3 | 3 | [3,5,7] | \(a_{n+1} = a_n + 2\times3\) |
| … | |||
| n | n | [3,5,7,9,11, … ,\(2n+1\)] | \(a_{n+1} = a_n + 2\times n\) |
如何并行计算※
- 在单机的情况下，尽量利用 CPU 多核的能力，并行度等于 CPU 物理核心的数量。因为超线程共享同一个物理核心的 ALU 计算单元，所以超线程对该程序的提升有限。
- 在集群的情况下，可以利用业内开源的 MapReduce 系统如 hadoop 来处理并行任务。
附录※
参赛的代码 SearchPrime
