素数

在算法竞赛，数论是绕不开的话题，而素数（或称质数）则是数论中最基础也最重要的核心概念之一。无论是直接考察素数性质，还是作为其他数论算法（如欧拉函数、模运算、因数分解）的基础，对素数深刻的理解和高效的算法掌握都是冲击奖牌的关键。

1. 素数基础 (Prime Basics)

1.1 定义

一个大于 1 的正整数 ，如果除了 1 和它本身以外，不能被其他正整数整除，那么 就被称为素数（质数）。大于 1 且不是素数的正整数称为合数。1 既不是素数也不是合数。

1.2 试除法判定素数 (Trial Division Primality Test)

这是最直观的素数判定方法。要判断一个整数 () 是否为素数，我们只需检查是否存在一个整数 使得 且 。如果存在这样的 ，则 是合数；否则， 是素数。

优化: 我们注意到，如果 是一个合数，它必然有一个小于或等于 的因子。因为如果 且 ，那么 和 中至少有一个不大于 。如果 且 ，则 ，这与 矛盾。

因此，我们只需要检查 到 之间的整数是否能整除 即可。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 功能：判断 n 是否为素数 (试除法)
// 参数：n - 待判断的整数
// 返回值：true 如果 n 是素数，false 否则
bool is_p(ll n) {
    if (n < 2) return false; // 小于2的数不是素数
    // 只需检查到 sqrt(n)
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false; // 找到因子，不是素数
        }
    }
    return true; // 没有找到小于等于 sqrt(n) 的因子，是素数
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    cin >> n;
    if (is_p(n)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

复杂度分析:

• 时间复杂度: 。对于单次判定，这个效率在 较大时（例如 或更大）是无法接受的。
• 空间复杂度: 。

局限性: 当需要判断大量数字，或者数字本身非常大时，试除法效率低下。我们需要更快的工具。

2. 素数筛法 (Sieving for Primes)

当我们需要找出一定范围内的所有素数时（例如 到 ），逐个使用试除法判断效率太低。总时间复杂度将达到 。筛法应运而生，它们能以更低的时间复杂度预处理出范围内的所有素数。

2.1 埃拉托斯特尼筛法 (Sieve of Eratosthenes)

这是最古老、最经典的素数筛法。其基本思想是：从 2 开始，将每个素数的倍数都标记为合数。

步骤:

1. 创建一个布尔数组 isp[] （或 vis[]，表示 visited），大小为 ，初始化所有元素为 true（或 false，看标记方式），表示所有数初始时都“可能是素数”。isp[0] 和 isp[1] 标记为 false。
2. 从 开始遍历到 ：
   • 如果 isp[i] 为 true，说明 是一个素数。
   • 将 的所有倍数 （不超过 ）标记为合数，即设置 isp[j] = false。
3. 遍历完成后，所有 isp[i] 仍为 true 的 就是范围内的素数。

优化:

• 标记倍数时，可以从 开始。因为对于 ， 这个合数一定在处理 时被 的某个素因子筛掉了。
• 外层循环只需要遍历到 即可标记所有合数，但为了得到所有素数列表，通常还是遍历到 。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e6 + 5; // 设定筛法上限
bool isp[N];         // isp[i] = false 表示 i 是素数, true 表示 i 是合数
vector<int> prm;     // 存储找到的素数

// 功能：埃氏筛法预处理 1 到 n 的素数
// 参数：n - 筛法上限
void sieve(int n) {
    fill(isp, isp + n + 1, false); // 初始化都为非合数（可能是素数）
    isp[0] = isp[1] = true;      // 0 和 1 不是素数

    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) { // 如果 i 是素数
            prm.push_back(i); // 记录素数
            // 从 i*i 开始标记，且 j 需为 long long 防止溢出
            for (ll j = (ll)i * i; j <= n; j += i) {
                isp[j] = true; // 标记 i 的倍数为合数
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n; // 输入筛法上限

    sieve(n);

    // 输出找到的素数个数
    cout << "Primes found: " << prm.size() << "\n";
    // 可以选择性打印素数
    // for (int p : prm) {
    //     cout << p << " ";
    // }
    // cout << "\n";

    // 示例：判断 1 到 n 之间的数是否为素数
    // for(int i = 1; i <= n; ++i) {
    //     if (!isp[i]) {
    //         cout << i << " is prime.\n";
    //     } else {
    //         cout << i << " is composite.\n";
    //     }
    // }

    return 0;
}

复杂度分析:

• 时间复杂度: 。直观上看是 。根据素数定理的推论，素数的倒数和近似于 。这是一个非常接近线性的复杂度，对于 在 甚至 级别都非常高效。
• 空间复杂度: ，主要用于存储 isp 数组。

2.2 线性筛 (Linear Sieve / Euler’s Sieve)

埃氏筛法虽然高效，但仍有冗余：一个合数会被它的多个素因子重复标记。例如，12 会被 2 标记一次，也会被 3 标记一次。线性筛的目标是让每个合数只被其 最小的素因子 标记一次，从而达到严格的 时间复杂度。

核心思想:

维持一个当前找到的素数列表 prm。遍历 从 2 到 。

1. 如果 没有被标记过，则 是素数，将其加入 prm 列表。
2. 对于 prm 中的每个素数 ：
   • 标记 为合数。
   • 关键: 如果 ，则停止用 prm 中更大的素数去标记 的倍数。
     • 原因: 如果 是 的倍数，即 ，那么对于 prm 中下一个更大的素数 ，合数 。这个合数的最小素因子显然是 （因为 且 是 的因子，所以也是 的因子）。根据线性筛的原则（每个合数只被其最小素因子筛一次）， 应该在后面遍历到 时，被 筛掉，而不是现在被 筛掉。因此，一旦 是 的倍数，就必须 break，保证 是被其最小素因子 筛掉的。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e7 + 5; // 线性筛通常能处理更大的范围
bool isp[N];         // isp[i] = true 表示 i 不是素数 (是合数或 0, 1)
int prm[N / 10];     // 存储素数，大小可以估算或动态分配，这里给个大概
int cnt = 0;         // 素数计数器

// 功能：线性筛预处理 1 到 n 的素数
// 参数：n - 筛法上限
void sieve(int n) {
    fill(isp, isp + n + 1, false);
    isp[0] = isp[1] = true;
    cnt = 0;

    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) { // i 是素数
            prm[cnt++] = i;
        }
        // 遍历已找到的素数 prm[j]
        for (int j = 0; j < cnt && (ll)i * prm[j] <= n; ++j) {
            isp[i * prm[j]] = true; // 标记 i * prm[j] 为合数
            // 关键：保证每个合数只被最小质因子筛掉
            if (i % prm[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n; // 输入筛法上限

    sieve(n);

    cout << "Primes found: " << cnt << "\n";
    // 输出前 10 个素数
    // for (int i = 0; i < min(cnt, 10); ++i) {
    //     cout << prm[i] << " ";
    // }
    // cout << "\n";

    return 0;
}

复杂度分析:

• 时间复杂度: 。每个合数 只会被其最小素因子 在 时标记一次。外层循环 次，内层 for 循环的 break 条件保证了每个合数只被访问一次。
• 空间复杂度: ，用于存储 isp 数组和 prm 数组（素数个数约为 ）。

应用场景:

线性筛是算法竞赛中预处理素数的最常用方法，尤其适用于需要 以内所有素数，或者需要在 时间内预处理某些数论函数（如欧拉函数 、莫比ウス函数 ）的场景。这些函数通常可以在线性筛的过程中一并计算出来。

3. 质因数分解 (Prime Factorization)

算术基本定理 (Fundamental Theorem of Arithmetic): 任何一个大于 1 的正整数 都可以唯一地分解为有限个素数的乘积，形式为：

其中 是素数， 是正整数。

质因数分解是数论问题的基石之一。

3.1 试除法分解 (Trial Division Factorization)

最朴素的方法是试除法。我们尝试用从 2 开始的整数去除 。

步骤:

1. 遍历 从 2 开始。
2. 如果 能整除 （即 ）：
   • 是 的一个质因子。记录 。
   • 将 中所有的因子 都除尽，即 直到 不能再被 整除。同时记录 的指数。
3. 继续增加 ，重复步骤 2。
4. 优化: 和素数判定类似，我们只需要尝试 到 即可。当循环结束时，如果 ，那么剩下的 本身一定是一个大于 的素因子。
   • 证明: 假设循环结束后 且 是合数，那么 必有一个小于等于 的素因子 。由于我们是从小到大尝试除数的，这个素因子 在之前的循环中一定会被尝试。如果 ，那么在循环到 时， 就会被 除尽，或者至少 的值会变小。如果 ，但仍然 (其中 是循环到 之前的 值)， 也会被除掉。只有当 在循环结束后剩下的值是一个大于 的素数时，才不会在 的循环中被除掉。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 功能：对 n 进行质因数分解 (试除法)
// 参数：n - 待分解的正整数
// 返回值：一个 map，键是质因子，值是其指数
map<ll, int> factorize(ll n) {
    map<ll, int> factors;
    if (n < 2) return factors; // 处理边界情况

    // 尝试 2 到 sqrt(n) 的因子
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) { // i 是一个因子
            int cnt = 0;
            while (n % i == 0) { // 除尽所有因子 i
                n /= i;
                cnt++;
            }
            factors[i] = cnt; // 记录质因子及其指数
        }
    }

    // 如果 n 在除完 <= sqrt(n) 的因子后仍然大于 1
    // 说明剩下的 n 是一个大于 sqrt(n_original) 的质因子
    if (n > 1) {
        factors[n] = 1;
    }

    return factors;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    cin >> n;

    map<ll, int> res = factorize(n);

    cout << n << " = ";
    bool first = true;
    for (auto const& [p, a] : res) {
        if (!first) {
            cout << " * ";
        }
        cout << p;
        if (a > 1) {
            cout << "^" << a;
        }
        first = false;
    }
    if (res.empty() && n >= 0) { // 处理 n=0, 1 的情况或 n 本身就是素数且小于等于1（虽然函数处理了<2）
        cout << n; // 保证输入 0 或 1 时有输出
    } else if (res.empty() && n < 0) {
         // 如果需要处理负数，可以先分解绝对值，再加负号
         cout << n;
    }
    cout << "\n";

    return 0;
}

复杂度分析:

• 时间复杂度: 。对于单个数的分解，这个效率在 达到 左右是可接受的，但对于 级别的 则不够快。
• 空间复杂度: 或 ，其中 是 的不同质因子个数。空间主要用于存储结果，因子个数通常不多。

优化: 如果需要对多个数进行质因数分解，且这些数范围不大（例如都在 以内），可以先用筛法预处理出范围内的所有素数，然后只用这些素数去试除，可以略微加速。但主要瓶颈仍然是 。

3.2 Pollard’s Rho 算法 (进阶)

对于非常大的数（例如 ）， 的试除法分解变得不可行。这时需要更高级的算法，Pollard’s Rho 是其中一种常用的 随机化 因子分解算法。

核心思想:

该算法试图利用随机函数在模 的某个因子 下产生的序列更快地出现循环（生日悖论的原理）来找到 的一个非平凡因子（不是 1 或 ）。

它使用一个伪随机序列 ，并检查 是否大于 1。通过 Floyd 判圈算法（快慢指针）来检测循环，即比较 和 。如果 ，则 可能是 的一个因子。

• 如果 ，说明这次尝试失败（可能选取的 或初始值 不好，或者 本身是素数），需要更换 或 重试。
• 如果 ，则找到了一个因子 。我们可以递归地对 和 进行分解。

注意: Pollard’s Rho 是随机算法，不能保证一定能快速找到因子，但在实践中对于 范围内的合数通常表现良好。它需要配合 Miller-Rabin 素数测试（见后文）一起使用：先用 Miller-Rabin 判断 是否很可能是素数，如果是合数再用 Pollard’s Rho 找因子。

复杂度: 启发式期望时间复杂度约为 。

代码实现: 由于涉及较多的细节（大数乘法取模、GCD、随机化、递归），Pollard’s Rho 的代码相对复杂。在 ICPC 竞赛中，如果不是专门准备数论难题的队伍，可能不会现场实现它，但了解其存在和适用场景是有益的。对于冲击金牌的选手，掌握 Pollard’s Rho 是必要的。

（注：此处不提供 Pollard’s Rho 的完整代码，因为它较为复杂且超出初学者/提高组的常规要求，其实现需要高效的模乘、模幂和 GCD 算法。）

4. 模运算与数论定理 (Modular Arithmetic & Theorems)

模运算是数论的基石，在算法竞赛中无处不在。素数在模运算中扮演着特殊的角色。

4.1 费马小定理 (Fermat’s Little Theorem)

定理叙述: 如果 是一个素数，并且整数 不是 的倍数（即 ，或 ），那么：

推论: 对于任意整数 （无论是否是 的倍数），都有：

应用:

1. 快速计算模幂的逆元: 当模数 是素数时，且 ，我们可以用费马小定理计算 在模 下的乘法逆元。因为 ，所以 。因此， 就是 的模 逆元。这需要配合快速幂算法（见下文）来高效计算 。
2. 概率性素数测试 (Fermat Primality Test): 如果对于一个数 ，我们随机选取几个 （满足 ），计算 。如果结果不为 1，则 必定是合数。如果对于所有选取的 结果都为 1，则 可能是素数。然而，存在一些合数（称为 Carmichael 数，例如 561）使得对于所有与其互质的 ，都有 ，因此费马测试是不可靠的，但它是更强的 Miller-Rabin 测试的基础。

快速幂 (Modular Exponentiation):

用于在 时间内计算 。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 功能：计算 (a^b) % m
// 参数：a - 底数, b - 指数, m - 模数
ll power(ll a, ll b, ll m) {
    ll res = 1;
    a %= m; // 预处理，防止 a 过大
    while (b > 0) {
        if (b & 1) { // 如果 b 的当前最低位是 1
            res = (__int128)res * a % m; // 使用 __int128 防止中间结果溢出
        }
        a = (__int128)a * a % m; // a = a^2 % m
        b >>= 1; // b = b / 2
    }
    return res;
}

// 功能：使用费马小定理计算 a 在模素数 p 下的逆元
// 要求：p 是素数，a % p != 0
ll mod_inv_fermat(ll a, ll p) {
    if (a % p == 0) return -1; // 无逆元或非法输入
    return power(a, p - 2, p); // 计算 a^(p-2) mod p
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll a, p;
    // 示例：计算 3 在模 7 下的逆元
    a = 3; p = 7; // p=7 是素数
    ll inv = mod_inv_fermat(a, p);
    cout << "Inverse of " << a << " mod " << p << " is " << inv << endl; // 3*5 = 15 = 1 (mod 7) -> inv = 5
    cout << "Check: (" << a << " * " << inv << ") % " << p << " = " << (a * inv % p) << endl;

    // 示例：计算 2^10 mod 1000000007 (一个大素数)
    a = 2; ll b = 10; p = 1000000007;
    cout << "2^10 mod " << p << " = " << power(a, b, p) << endl;


    return 0;
}

注意: 在计算 res = res * a % m 和 a = a * a % m 时，如果 都是 long long 级别（例如 ），它们的乘积可能会超过 long long 的范围（约 ）。上述代码中使用了 __int128 来处理中间结果，这是 g++/clang 的一个扩展类型，可以存储更大的整数。如果编译器不支持 __int128，则需要使用更复杂的“龟速乘”（二进制乘法）或者基于 long double 的近似技巧来避免溢出。对于标准 ICPC 规则，通常允许使用 __int128。

快速幂复杂度: 时间复杂度， 空间复杂度（递归实现则为 栈空间）。

4.2 欧拉定理 (Euler’s Theorem)

费马小定理是欧拉定理在模数为素数时的特例。欧拉定理适用于模数为任意正整数的情况。

欧拉函数 (Euler’s Totient Function) :
定义为小于或等于 的正整数中与 互质（最大公约数为 1）的数的个数。

计算 :
如果 的标准质因数分解为 ，则 的计算公式为：

展开后也可以写成：

性质:

• 如果 是素数，。
• 如果 是素数，，则 。
• 欧拉函数是 积性函数：如果 ，则 。

欧拉定理叙述: 如果整数 和正整数 互质（即 ），那么：

扩展欧拉定理 (或称欧拉降幂公式):
对于任意整数 和正整数 ，以及任意整数 ，有：

注意: 这个扩展定理 不要求 与 互质。当 时，指数不能简单地对 取模，需要加上 来保证正确性（仅当 时才需要判断，若 则直接套用公式）。

应用:

1. 计算模幂逆元 (通用情况): 如果 ，则 模 的逆元是 。这需要先计算 。
2. 指数降幂: 在计算 时，如果指数 非常大，可以使用欧拉定理（或扩展欧拉定理）将指数 对 （或在某些情况下是 再加 ）取模，从而减小指数的规模。这对于处理形如 的问题非常有用。

计算 的方法:

• 单个计算: 利用质因数分解公式。先对 进行质因数分解 ，然后套用公式 。时间复杂度主要取决于质因数分解，即 。

  #include <bits/stdc++.h>
  
  using namespace std;
  using ll = long long;
  
  // 功能：计算 phi(n) (基于质因数分解)
  // 参数：n - 正整数
  // 返回值：phi(n)
  ll phi(ll n) {
      if (n == 0) return 0; // phi(0) 无定义或视情况处理
      ll res = n;
      for (ll i = 2; i * i <= n; ++i) {
          if (n % i == 0) {
              res = res / i * (i - 1); // 等价于 res *= (1 - 1/i)
              while (n % i == 0) {
                  n /= i;
              }
          }
      }
      if (n > 1) { // 如果最后剩下一个大于 sqrt(n_original) 的质因子
          res = res / n * (n - 1);
      }
      return res;
  }
  
  int main() {
      ios::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
  
      ll n;
      cin >> n;
      cout << "phi(" << n << ") = " << phi(n) << endl;
      return 0;
  }

  复杂度: 。

• 批量计算 (线性筛): 可以在线性筛的同时计算出 到 所有数的欧拉函数值。

  #include <bits/stdc++.h>
  
  using namespace std;
  using ll = long long;
  
  const int N = 1e7 + 5;
  bool isp[N];
  int prm[N / 10];
  int cnt = 0;
  int phi_val[N]; // 存储 phi 值
  
  // 功能：线性筛计算 1 到 n 的 phi 值
  // 参数：n - 上限
  void sieve_phi(int n) {
      fill(isp, isp + n + 1, false);
      isp[0] = isp[1] = true;
      phi_val[1] = 1; // phi(1) = 1
      cnt = 0;
  
      for (int i = 2; i <= n; ++i) {
          if (!isp[i]) { // i 是素数
              prm[cnt++] = i;
              phi_val[i] = i - 1; // phi(p) = p - 1
          }
          for (int j = 0; j < cnt && (ll)i * prm[j] <= n; ++j) {
              int pj = prm[j];
              isp[i * pj] = true;
              if (i % pj == 0) { // pj 是 i 的最小质因子
                  // phi(i * pj) = phi(i) * pj
                  // 因为 i 包含了 pj, i*pj 与 i 相比，只是 pj 的指数增加了 1
                  // 根据 phi(p^k) = p^(k-1)(p-1) 推导
                  phi_val[i * pj] = phi_val[i] * pj;
                  break;
              } else { // pj 不是 i 的最小质因子 (即 gcd(i, pj) = 1)
                  // phi 是积性函数: phi(i * pj) = phi(i) * phi(pj)
                  phi_val[i * pj] = phi_val[i] * (pj - 1); // phi(pj) = pj - 1
              }
          }
      }
  }
  
  int main() {
      ios::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
  
      int n;
      cin >> n;
  
      sieve_phi(n);
  
      // 打印前 10 个 phi 值
      for (int i = 1; i <= min(n, 10); ++i) {
          cout << "phi(" << i << ") = " << phi_val[i] << "\n";
      }
  
      return 0;
  }

  复杂度: 时间复杂度， 空间复杂度。

4.3 模逆元 (Modular Inverse)

给定整数 和 ，如果存在一个整数 使得 ，则称 是 模 的乘法逆元。记作 。

存在条件: 模 的逆元存在的充要条件是 。

求解方法:

1. 费马小定理: 当 是素数且 时，逆元为 。需要 的快速幂。

2. 欧拉定理: 当 时，逆元为 。需要计算 （若单次计算是 或 预处理 ）和快速幂 。

3. 扩展欧几里得算法 (Extended Euclidean Algorithm, ExGCD):
   这是求解模逆元最通用和常用的方法，因为它不要求 是素数，只需要 。
   扩展欧几里得算法用于求解方程 的一组整数解 。
   如果 ，那么方程变为 。对这个方程两边同时取模 ，得到 。因此，ExGCD 算出的 (可能需要调整到 范围内) 就是 模 的逆元。

   代码实现 (ExGCD):

   #include <bits/stdc++.h>
   
   using namespace std;
   using ll = long long;
   
   // 功能：扩展欧几里得算法，求解 ax + by = gcd(a, b)
   // 参数：a, b - 输入整数
   //       x, y - 引用参数，返回方程的一组特解
   // 返回值：gcd(a, b)
   ll exgcd(ll a, ll b, ll &x, ll &y) {
       if (b == 0) {
           x = 1;
           y = 0;
           return a;
       }
       ll d = exgcd(b, a % b, y, x); // 注意 x, y 的位置交换
       y -= (a / b) * x;
       return d;
   }
   
   // 功能：计算 a 模 n 的逆元 (使用 ExGCD)
   // 要求：gcd(a, n) = 1
   // 返回值：a 的模 n 逆元，若不存在则返回 -1 (或其他错误标记)
   ll mod_inv_exgcd(ll a, ll n) {
       ll x, y;
       ll d = exgcd(a, n, x, y);
       if (d != 1) {
           return -1; // 逆元不存在
       }
       // x 可能是负数，调整到 [0, n-1] 范围
       return (x % n + n) % n;
   }
   
   int main() {
       ios::sync_with_stdio(0);
       cin.tie(0);
       cout.tie(0);
   
       ll a, n;
       // 示例：计算 3 模 7 的逆元
       a = 3; n = 7;
       ll inv = mod_inv_exgcd(a, n);
       if (inv != -1) {
           cout << "Inverse of " << a << " mod " << n << " is " << inv << endl; // 5
       } else {
           cout << "Inverse does not exist." << endl;
       }
   
       // 示例：计算 6 模 9 的逆元
       a = 6; n = 9; // gcd(6, 9) = 3 != 1
       inv = mod_inv_exgcd(a, n);
       if (inv != -1) {
           cout << "Inverse of " << a << " mod " << n << " is " << inv << endl;
       } else {
           cout << "Inverse does not exist." << endl; // 不存在
       }
   
       return 0;
   }

   复杂度: 扩展欧几里得算法的时间复杂度与欧几里得算法相同，为 或 。

选择哪种方法?

• 如果模数 是素数，费马小定理最简单直接。
• 如果模数 不是素数，或者需要处理 是素数和合数混合的情况，扩展欧几里得算法是标准做法。
• 欧拉定理法需要计算 ，通常不如 ExGCD 直接。但在某些需要预计算 值的场景下也可行。

5. 大素数判定 (Large Primality Testing)

当需要判断的数 非常大（例如 甚至更大），试除法 和筛法 都不适用。这时需要概率性素数测试算法。

5.1 Miller-Rabin 算法

Miller-Rabin 是目前在算法竞赛中最常用的大数素性测试算法。它是一种 随机化算法，能够在 的时间内以非常高的概率判断一个数 是否为素数（ 是测试的轮数）。

核心思想:

基于费马小定理和二次探测定理。

1. 二次探测定理: 如果 是一个素数，且 是一个整数使得 ，则方程 的解只有 或 。
   • 推论: 如果找到一个 使得 但 且 ，则 一定是合数。

算法步骤:

1. 处理小情况: 如果 ，则 不是素数。如果 或 ，则 是素数。如果 是偶数且 ，则 是合数。
2. 分解 : 将 表示为 ，其中 是奇数，。
3. 进行 轮测试:
   • 随机选择一个整数 ，满足 。（实践中通常选择一些小的素数作为基底 ，例如 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}。对于 的范围，使用特定的几组基底就能做到 100% 确定性判断）。
   • 计算 。
   • 如果 或 ，则 可能是素数，继续下一轮测试（或换一个基底 ）。
   • 否则，进行 次平方探测：
     • 重复 次：令 。
     • 如果在某次平方后 ，则 可能是素数，跳出内层循环，继续下一轮测试。
     • 如果在某次平方后 （但之前的 不是 ），根据二次探测定理， 是合数，直接返回 false。
   • 如果 次循环（包括初始的 ）结束后， 仍然不等于 ，则说明费马小定理 不成立（或者在中间步骤违反了二次探测），因此 是合数，返回 false。
4. 通过所有测试: 如果 通过了 轮测试（对于所有选定的基底 ），则我们 高度确信 是素数，返回 true。

确定性基底: 对于 ，使用以下基底 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 进行测试，可以得到确定性的结果（如果通过则一定是素数）。在 ICPC 中常用这组基底。

代码实现 (Miller-Rabin):

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// 使用 __int128 防止模乘溢出
using i128 = __int128;

// 快速幂 (底数和模数可能很大)
ll power(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (i128)res * a % m;
        a = (i128)a * a % m;
        b >>= 1;
    }
    return res;
}

// Miller-Rabin 单轮测试
// n: 待测数, a: 基底
bool miller_rabin_check(ll n, ll a) {
    if (a % n == 0) return true; // a=0 或 a 是 n 的倍数，无法判断，视为通过

    ll d = n - 1;
    while (d % 2 == 0) d /= 2; // n-1 = 2^s * d

    ll x = power(a, d, n); // 计算 a^d mod n

    if (x == 1 || x == n - 1) return true; // 可能为素数

    while (d != n - 1) {
        x = (i128)x * x % n; // x = x^2 mod n
        d *= 2;             // 对应指数 d*2

        if (x == 1) return false; // 二次探测失败，一定是合数 (因为之前的 x != n-1)
        if (x == n - 1) return true; // 通过二次探测，可能为素数
    }

    // 循环结束 x 仍不为 n-1，说明 a^(n-1) != 1 mod n
    return false; // 合数
}

// Miller-Rabin 素性测试主函数
// n: 待测数
// k: 测试轮数 (或使用确定性基底时忽略)
bool is_prime_mr(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false; // 偶数

    // 使用确定性基底 (对于 n < 2^64)
    // ll bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; // 适用于较小范围
    ll bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; // 适用于 n < 2^64

    for (ll a : bases) {
        if (n == a) return true; // n 本身就是基底之一
        if (!miller_rabin_check(n, a)) {
            return false; // 只要有一轮失败，就是合数
        }
    }

    return true; // 通过所有确定性基底测试，是素数
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    // 测试一些数
    ll tests[] = {2, 3, 4, 17, 561, 1000000007, 999999999989LL, 1000000000000000003LL};

    for (ll t : tests) {
        if (is_prime_mr(t)) {
            cout << t << " is prime.\n";
        } else {
            cout << t << " is composite.\n";
        }
    }
    // 561 is composite. (Carmichael number)
    // 999999999989 is prime.
    // 1000000000000000003 is prime.

    return 0;
}

复杂度分析:

• 时间复杂度: 一次 miller_rabin_check 的复杂度主要是快速幂和平方探测，约为 （如果认为模乘是 ）或 （如果认为模乘是 或 ，这取决于实现，通常视为 或更快）。进行 轮测试，总复杂度为 或 。使用确定性基底时 是常数。
• 空间复杂度: (不计 __int128 的开销)。

适用场景: 判断 到 甚至更大范围内的单个整数是否为素数。是 Pollard’s Rho 分解算法的前置步骤。

6. 实战

1. 整数溢出: 在处理大数时，尤其是乘法和快速幂中，中间结果很容易超过 long long 的范围。务必使用 __int128 (如果可用) 或实现防溢出模乘（龟速乘）。
2. 选择合适的算法:
   • 判断单个小整数（如 ）是否为素数：可以直接用预处理的筛法 isp[] 数组 查询。
   • 判断单个中等整数（如 ）是否为素数：试除法 可能可行。
   • 判断单个大整数（如 或更大）：必须用 Miller-Rabin 。
   • 找出 到 ( 或 ) 的所有素数：线性筛 是最佳选择。埃氏筛 也可以。
   • 质因数分解小整数（）：可以结合筛法预处理素数，再用这些素数试除，复杂度仍是 或更快（如果因子都很小）。
   • 质因数分解中等整数（）：试除法 。
   • 质因数分解大整数（）：先用 Miller-Rabin 判素，如果是合数，用 Pollard’s Rho 尝试分解。
3. 边界条件: 注意处理 等特殊情况。负数通常不讨论素性，但如果题目涉及，需明确定义或按题意处理。
4. 复杂度意识: 时刻关注算法的时间和空间复杂度是否满足题目限制。尤其是在循环嵌套或递归中。
5. 模板化: 将筛法、快速幂、ExGCD、Miller-Rabin 等常用数论算法写成可靠的模板，比赛时可以快速调用。
6. 组合使用: 很多数论题需要结合多种技术，例如先筛素数，再用素数进行分解或计算欧拉函数，最后结合模运算定理求解。

7. 总结

素数是数论世界的基础构件，掌握素数相关的核心概念和高效算法是必备技能。

• 基础: 理解素数定义，掌握 的试除法判定和分解。
• 核心: 精通埃氏筛 和线性筛 ，能在 内预处理素数及相关积性函数（如 ）。
• 进阶: 熟练运用费马小定理、欧拉定理进行模逆元计算和指数降幂，掌握 的快速幂和扩展欧几里得算法。
• 高阶: 掌握 的 Miller-Rabin 大数素性测试，了解 的 Pollard’s Rho 大数分解算法。
• 实战: 注意数据范围、整数溢出、边界条件，根据问题规模选择最合适的算法，并能够灵活组合运用这些工具。