素数

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

素数计数函数：小于或等于 $x$ 的素数的个数，用 $\pi (x)$ 表示。随着 $x$ 的增大，有这样的近似结果：$\pi (x)\sim {\displaystyle \frac{x}{\ln \left(x\right)}}$。

素性测试

素性测试（Primality test）可以用于判定所给自然数是否为素数。

素性测试有两种：

1. 确定性测试：绝对确定一个数是否为素数。常见例子包括试除法、Lucas–Lehmer 测试和椭圆曲线素性证明。
2. 概率性测试：通常比确定性测试快很多，但有可能（尽管概率很小）错误地将 合数 识别为质数（尽管反之则不会）。因此，通过概率素性测试的数字被称为 可能素数，直到它们的素数可以被确定性地证明。而通过测试但实际上是合数的数字则被称为 伪素数。有许多特定类型的伪素数，最常见的是费马伪素数，它们是满足费马小定理的合数。概率性测试的常见例子包括 Miller–Rabin 测试。

试除法

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

参考实现

C++Python

bool isPrime(int a) {
  if (a < 2) return false;
  for (int i = 2; i < a; ++i)
    if (a % i == 0) return false;
  return true;
}

def isPrime(a):
    if a < 2:
        return False
    for i in range(2, a):
        if a % i == 0:
            return False
    return True

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

很容易发现这样一个事实：如果 $x$ 是 $a$ 的约数，那么 $\frac{a}{x}$ 也是 $a$ 的约数。

这个结论告诉我们，对于每一对 $(x,\frac{a}{x})$，只检验其中的一个就足够了。为了方便起见，我们只考察每一对的较小数。不难发现，所有这些较小数都在 $[1,\sqrt{a}]$ 这个区间里。

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

参考实现

C++Python

bool isPrime(int a) {
  if (a < 2) return 0;
  for (int i = 2; (long long)i * i <= a; ++i)  // 防溢出
    if (a % i == 0) return 0;
  return 1;
}

def isPrime(a):
    if a < 2:
        return False
    for i in range(2, int(sqrt(a)) + 1):
        if a % i == 0:
            return False
    return True

Fermat 素性测试

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

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

基本思想是不断地选取在 $[2,n-1]$ 中的基 $a$，并检验是否每次都有 $a^{n-1}\equiv 1(\mathrm{mod}n)$。

参考实现

C++Python

bool fermat(int n) {
  if (n < 3) return n == 2;
  // test_time 为测试次数,建议设为不小于 8
  // 的整数以保证正确率,但也不宜过大,否则会影响效率
  for (int i = 1; i <= test_time; ++i) {
    int a = rand() % (n - 2) + 2;
    if (quickPow(a, n - 1, n) != 1) return false;
  }
  return true;
}

def fermat(n):
    if n < 3:
        return n == 2
    # test_time 为测试次数,建议设为不小于 8
    # 的整数以保证正确率,但也不宜过大,否则会影响效率
    for i in range(1, test_time + 1):
        a = random.randint(0, 32767) % (n - 2) + 2
        if quickPow(a, n - 1, n) != 1:
            return False
    return True

如果 $a^{n-1}\equiv 1(\mathrm{mod}n)$ 但 $n$ 不是素数，则 $n$ 被称为以 $a$ 为底的 伪素数。我们在实践中观察到，如果 $a^{n-1}\equiv 1(\mathrm{mod}n)$，那么 $n$ 通常是素数。但这里也有个反例：如果 $n=341$ 且 $a=2$，即使 $341=11\cdot 31$ 是合数，有 $2^{340}\equiv 1(\mathrm{mod}341)$。事实上，$341$ 是最小的伪素数基数。

很遗憾，费马小定理的逆定理并不成立，换言之，满足了 $a^{n-1}\equiv 1(\mathrm{mod}n)$，$n$ 也不一定是素数。甚至有些合数 $n$ 满足对任意满足 $a\perp n$ 的整数 $a$ 均有 $a^{n-1}\equiv 1(\mathrm{mod}n)$，这样的数称为 Carmichael 数。

Carmichael 函数

对正整数 $n$，定义 Carmichael 函数（卡迈克尔函数）为对任意满足 $(a,n)=1$ 的整数 $a$，使

$$a^m\equiv 1(\mathrm{mod}n)$$

恒成立的最小正整数 $m$.

即：

$$\lambda (n)=max\{{\delta }_n(a):(a,n)=1\}$$

Carmichael 函数有如下性质：

1. （Carmichael 定理）对任意素数 $p$ 和任意正整数 $r$，

   $$\lambda \left(p^r\right)=\{\begin{array}{ll}\frac{1}{2}\phi \left(p^r\right),& p=2\wedge r\ge 3,\\ \phi \left(p^r\right),& \text{otherwise}.\end{array}$$
   证明

   该定理等价于：

   若模 $n=p^r$ 有 原根，则 $\lambda (n)=\phi (n)$，否则 $\lambda (n)={\displaystyle \frac{1}{2}}\phi (n)$.

   当模 $p^r$ 有原根时，由 原根存在定理 可知命题成立。否则 $p=2$ 且 $r\ge 3$，我们有：

   $$\lambda \left(2^r\right)\mid 2^{r-2}$$

   又由 $5^{2^{r-3}}\equiv 1+2^{r-1}(\mathrm{mod}{2}^{r-2})$ 知 $\lambda \left(2^r\right)>2^{r-3}$，因此

   $$\lambda \left(p^r\right)=2^{r-2}=\frac{1}{2}\phi \left(p^r\right)$$

   进而有：

   1. 对任意正整数 $n$，有 $\lambda (n)\mid \phi (n)$

   2. 对任意正整数 $a$，$b$，有 $a\mid b⟹\lambda (a)\mid \lambda (b)$

2. 令 $n$ 的唯一分解式为 $n=\prod _{i=1}^k{p}_i^{r_i}$，则

   $$\lambda (n)=[\lambda \left(p_1^{r_1}\right),\lambda \left(p_2^{r_2}\right),\dots ,\lambda \left(p_k^{r_k}\right)]$$

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

   进而有：

   1. 对任意正整数 $a$，$b$，有 $\lambda ([a,b])=[\lambda (a),\lambda (b)]$

Carmichael 数

对于合数 $n$，如果对于所有正整数 $a$，$a$ 和 $n$ 互素，都有同余式 $a^{n-1}\equiv 1(\mathrm{mod}n)$ 成立，则合数 $n$ 为 Carmichael 数（卡迈克尔数，OEIS:A002997）。

比如 $561=3\times 11\times 17$ 就是一个 Carmichael 数，同时也是最小的 Carmichael 数。

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

Korselt 判别法[^korselt1899probleme]

合数 $n$ 是 Carmichael 数当且仅当 $n$ 无平方因子且对 $n$ 的任意质因子 $p$ 均有 $p-1\mid n-1$.

上述判别法可简化为：

Carmichael 数判别法

合数 $n$ 是 Carmichael 数当且仅当 $\lambda (n)\mid n-1$，其中 $\lambda (n)$ 为 Carmichael 函数。

Carmichael 数有如下性质：

1. Carmichael 数无平方因子且至少有 $3$ 个不同的质因子。

2. 设 $C(n)$ 为小于 $n$ 的 Carmichael 数个数，则：

   1. （Alford, Granville, Pomerance. 1994[^alford1994infinitely]）$C(n)>n^{2/7}$。

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

   2. （Erdős. 1956[^erdos1956pseudoprimes]）$C(n)

---

本页面最近更新：2025/7/17 08:50:55，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Tiphereth-A, Xeonacid, c-forrest, Enter-tainer, StudyingFather, iamtwz, ksyx, Marcythm, MegaOwIer, 383494, Alpacabla, abc1763613206, alphagocc, Backl1ght, CCXXXI, drkelo, Early0v0, Great-designer, greyqz, GuanghaoYe, H-J-Granger, HeRaNO, HHH2309, isdanni, kenlig, lazyasn, Menci, ouuan, r-value, shawlleyw, shopee-jin, shuzhouliu, Siger Young, TrisolarisHD, untitledunrevised, void-mian, Voileexperiments, weilycoder, xtlsoft, yusancky, YuzhenQin1
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用