素数与合数的定义，见 数论基础。

素数计数函数：小于或等于 的素数的个数，用 表示。随着 的增大，有这样的近似结果：。

我们自然地会想到，如何用计算机来判断一个数是不是素数呢？

暴力做法自然可以枚举从小到大的每个数看是否能整除

这样做是十分稳妥了，但是真的有必要每个数都去判断吗？

很容易发现这样一个事实：如果 是 的约数，那么 也是 的约数。

这个结论告诉我们，对于每一对 ，只需要检验其中的一个就好了。为了方便起见，我们之考察每一对里面小的那个数。不难发现，所有这些较小数就是 这个区间里的数。

由于 肯定是约数，所以不检验它。

素性测试（Primality test）是一类在 不对给定数字进行素数分解（prime factorization）的情况下，测试其是否为素数的算法。

素性测试有两种：

接下来我们将着重介绍几个概率性素性测试：

Fermat 素性检验 是最简单的概率性素性检验。

我们可以根据 费马小定理 得出一种检验素数的思路：

基本思想是不断地选取在 中的基 ，并检验是否每次都有 。

如果 但 不是素数，则 被称为以 为底的 伪素数。我们在实践中观察到，如果 ，那么 通常是素数。但这里也有个反例：如果 且 ，即使 是合数，有 。事实上， 是最小的伪素数基数。

很遗憾，费马小定理的逆定理并不成立，换言之，满足了 ， 也不一定是素数。甚至有些合数 满足对任意满足 的整数 均有 ，这样的数称为 Carmichael 数。

对正整数 ，定义 Carmichael 函数（卡迈克尔函数）为对任意满足 的整数 ，使

恒成立的最小正整数 .

即：

Carmichael 函数有如下性质：

（Carmichael 定理）对任意素数 和任意正整数 ，

该定理等价于：

若模 有 原根，则 ，否则 .

当模 有原根时，由 原根存在定理 可知命题成立。否则 且 ，我们有：

又由 知 ，因此

进而有：

对任意正整数 ，有

对任意正整数 ，，有

令 的唯一分解式为 ，则

由 中国剩余定理 和 Carmichael 定理易证。

进而有：

对于合数 ，如果对于所有正整数 ， 和 互素，都有同余式 成立，则合数 为 Carmichael 数（卡迈克尔数，OEIS:A002997）。

比如 就是一个 Carmichael 数，同时也是最小的 Carmichael 数。

我们可以用如下方法判断合数 是否为 Carmichael 数：

合数 是 Carmichael 数当且仅当 无平方因子且对 的任意质因子 均有 .

上述判别法可简化为：

合数 是 Carmichael 数当且仅当 ，其中 为 Carmichael 函数。

Carmichael 数有如下性质：

设 为小于 的 Carmichael 数个数，则：

（Alford, Granville, Pomerance. 19942）

由此可知 Carmichael 数有无限多个。

（Erdős. 19563），其中 为常数。

由此可知 Carmichael 数的分布十分稀疏。实际上 ，4.

「若 为 Carmichael 数，则 也为 Carmichael 数」是错误的。

如 为 Carmichael 数，考虑 。

注意到 ，由 Korselt 判别法知，若 是 Carmichael 数，则 和 均为 的因子。

而 ，故 ，因此 不是 Carmichael 数。

Miller–Rabin 素性测试（Miller–Rabin primality test）是进阶的素数判定方法。它是由 Miller 和 Rabin 二人根据费马小定理的逆定理（费马测试）优化得到的。因为和许多类似算法一样，它是使用伪素数的概率性测试，我们必须使用慢得多的确定性算法来保证素性。然而，实际上没有已知的数字通过了高级概率性测试（例如 Miller–Rabin）但实际上却是复合的。因此我们可以放心使用。

在不考虑乘法的复杂度时，对数 进行 轮测试的时间复杂度是 。Miller-Rabbin 素性测试常用于对高精度数进行测试，此时时间复杂度是 ，利用 FFT 等技术可以优化到 。

如果 是奇素数，则 的解为 或者 。

要证明该定理，只需将上面的方程移项，再使用平方差公式，得到 ，即可得出上面的结论。

根据卡迈克尔数的性质，可知其一定不是 。

不妨将费马小定理和二次探测定理结合起来使用：

将 中的指数 分解为 ，在每轮测试中对随机出来的 先求出 ，之后对这个值执行最多 次平方操作，若发现非平凡平方根时即可判断出其不是素数，否则再使用 Fermat 素性测试判断。

还有一些实现上的小细节：

这样得到了较正确的 Miller Rabin：（来自 fjzzq2002）

另外，假设 广义 Riemann 猜想（generalized Riemann hypothesis, GRH）成立，则对数 最多只需要测试 中的全部整数即可 确定 数 的素性，证明参见注释 7。

而在 OI 范围内，通常都是对 范围内的数进行素性检验。对于 范围内的数，选取 三个数作为基底进行 Miller–Rabin 素性检验就可以确定素性；对于 范围内的数，选取 七个数作为基底进行 Miller–Rabin 素性检验就可以确定素性。参见注释 8。

也可以选取 （即前 个素数）检验 范围内的素数。

注意如果要使用上面的数列中的数 作为基底判断 的素性：

顾名思义，素数就是因子只有两个的数，那么反素数，就是因子最多的数（并且因子个数相同的时候值最小），所以反素数是相对于一个集合来说的。

一种符合直觉的反素数定义是：在一个正整数集合中，因子最多并且值最小的数，就是反素数。

如果某个正整数 满足如下条件，则称为是 反素数：任何小于 的正数的约数个数都小于 的约数个数。

注意区分 emirp，它表示的是逐位反转后是不同素数的素数（如 149 和 941 均为 emirp，101 不是 emirp）。

那么，如何来求解反素数呢？

首先，既然要求因子数，首先要做的就是素因子分解。把 分解成 的形式，其中 是素数， 为他的指数。这样的话总因子个数就是 。

但是显然质因子分解的复杂度是很高的，并且前一个数的结果不能被后面利用。所以要换个方法。

我们来观察一下反素数的特点。

反素数肯定是从 开始的连续素数的幂次形式的乘积。

数值小的素数的幂次大于等于数值大的素数，即 中，有

解释：

如果不是从 开始的连续素数，那么如果幂次不变，把素数变成数值更小的素数，那么此时因子个数不变，但是 的数值变小了。交换到从 开始的连续素数的时候 值最小。

如果数值小的素数的幂次小于数值大的素数的幂，那么如果把这两个素数交换位置（幂次不变），那么所得的 因子数量不变，但是 的值变小。

另外还有两个问题，

对于给定的 ，要枚举到哪一个素数呢？

最极端的情况大不了就是 ，所以只要连续素数连乘到刚好小于等于 就可以的呢。再大了，连全都一次幂，都用不了，当然就是用不到的啦！

我们要枚举到多少次幂呢？

我们考虑一个极端情况，当我们最小的素数的某个幂次已经比所给的 （的最大值）大的话，那么展开成其他的形式，最大幂次一定小于这个幂次。unsigned long long 的最大值是 ，所以可以枚举到 。

细节有了，那么我们具体如何具体实现呢？

我们可以把当前走到每一个素数前面的时候列举成一棵树的根节点，然后一层层的去找。找到什么时候停止呢？

当前走到的数字已经大于我们想要的数字了

当前枚举的因子已经用不到了（和 重复了嘻嘻嘻）

当前因子大于我们想要的因子了

当前因子正好是我们想要的因子（此时判断是否需要更新最小 ）

然后 dfs 里面不断一层一层枚举次数继续往下迭代可以。

求具有给定除数的最小自然数。请确保答案不超过 。

对于这种题，我们只要以因子数为 dfs 的返回条件基准，不断更新找到的最小值就可以了

大家都知道我们使用十进制记数法，即记数的基数是 。历史学家说这是因为人有十个手指，也许他们是对的。然而，这通常不是很方便，十只有四个除数——、、 和 。因此，像 、 或 这样的分数不便于用十进制表示。从这个意义上说，以 、 甚至 为底会方便得多。主要原因是这些数字的除数要大得多——分别是 、 和 。请回答：除数最多的不超过 的数是多少？

思路同上，只不过要改改 dfs 的返回条件。注意这样的题目的数据范围，32 位整数可能溢出。

Korselt, A. R. (1899). "Problème chinois".L'Intermédiaire des Mathématiciens.6: 142–143. ↩

W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers".Annals of Mathematics. 140 (3): 703–722. ↩

Erdős, P. (1956). "On pseudoprimes and Carmichael numbers".Publ. Math. Debrecen. 4 (3–4): 201–206. ↩

PINCH, Richard GE. The Carmichael numbers up to . ↩