3,317,044,064,679,887,385,961,980之内最大的素数是？

面对这样一个大数，要找到其范围内最大的素数所需要的计算量是非常之大的。

很容易发现素数的密度是越来越稀的，倘若我们能够获得素数分布的大致规律再加上素性检测的方法，我们就能相对快的找到一个大数之内最大的素数。

关于素数分布的规律高斯给过一个，另外还有更加“精确”的，在这里我就不再赘述。

现在的问题仅是素性检测了。

有这么一个公式接近素性判定的功能

如果p是任意一个不能整除整数a的素数，那么

然而存在这样一些合数，对于所有跟p互质的整数a，都满足费马小定理。这样的合数人类称它为开迈克尔数。

对于足够大的n，1-n内卡迈克尔数至少有：n的2/7次方个

目前来看我提高素性判定精确度的途径大致有两条：

显然我们可以利用费马小定理得到相关的推论，伪素数可以满足费马小定理但不一定能够满足其所有推论。

另外，我们可以通过增加底数的方式来提高素数判定的可信度。

首先我们对费马小定理进行推演

我们将1移到左边，得到：

令p-1=（2^i）*b (b为一奇数，因为p是一个不能整除整数a的素数，p肯定是一个奇数，因此p-1为一偶数)：

同余符号两边持续开方，直到：

即：

这是我们熟悉的x的平方减1的形式

在这里，令c=a^b,同时我们保持c为小于p的整数。则c+1=p,或c-1=0。

所以有：

即：

现在，我可以得到这样的推论：

即对a的指数p-1不断提取2这个因子，直到和p-1是模p是同余的，如果与1同余，则继续提取2这个因子，直到2被提取完，最后与p-1或1是模p同余的。

这种素数检测被称为 Miller-Rabin 测试。能通过Miller-Rabin测试的合数，我们称之为强伪素数。当a=2时，第一个强伪素数是2047。当同时检测a=2和a=3时，第一个强伪素数为1373653。我们可以发现，比单纯的费马检测要强有力的多。

关于底数的选择，相关的研究和论文都比较多，有很多现成的结论可供使用。

我们将a的p-1次方展开：

利用求模运算的性质，我们可将问题拆解为每一项的模的乘积。而具体的每一项我们可以通过转换成二进制以减小每一项的运算负担。听上去有点“混沌”，我这里将p-1展开：

a显然为0或1，因此计算量大大降低了

这是我独立完成的首个代码，在我的github上可以找到它maxprime

如果要考虑扩大程序的应用范围，可以引入AKS