题目链接

【模板】Pollard-Pho算法

题目描述

给定 组测试数据，对于每个正整数 （），判断它是否为质数。

解题思路

本题要求对一个大整数进行素性检验。当 的范围达到 时，传统的试除法（时间复杂度为 ）会超时。因此，我们需要使用更高效的算法。

米勒-拉宾素性检验（Miller-Rabin Primality Test） 是解决此类问题的标准算法。它是一种概率性测试，但通过精心选择一组“基底”（bases），可以对 long long 范围内的数进行确定性的判断。

算法核心原理

米勒-拉宾检验基于费马小定理和二次探测定理：

  1. 费马小定理：如果 是一个质数，且 是任何不能被 整除的整数，则有 。
  2. 二次探测定理：如果 是一个质数，且 ，则 或 。

米勒-拉宾检验巧妙地利用了这些性质。首先，我们将 分解为 的形式，其中 是奇数。然后，我们选取一个基底 ，计算 。

根据费马小定理，如果 是质数，那么 。 在计算这个幂次序列 的过程中，如果某一步的值 ，但 既不是 也不是 ，那么根据二次探测定理的逆否命题，我们就找到了 是合数的证据。

算法流程

  1. 处理边界情况：

    • 如果 ，不是质数。
    • 如果 或 ，是质数。
    • 如果 是大于 2 的偶数，不是质数。

  2. 分解 ：找到 和 ，使得 ，其中 为奇数。

  3. 进行检验：

    • 对于一个预选的基底 （）：
      a. 计算 。
      b. 如果 或 ，则 通过了这次检验，可能为质数。
      c. 否则，进行 次循环：将 更新为 。如果新的 值为 ，则 通过了检验。如果中途 变为 ，则说明 是合数。
      d. 如果在所有 次平方后， 仍不等于 ，则 是合数。

  4. 多次检验：为了保证结果的准确性，我们需要对多个基底 重复上述过程。对于 范围内的数据，使用以下 12 个基底 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 进行检验，就能得到 100% 准确的结果。

实现细节：大数乘法

在计算 和 时，由于 可达 ，中间乘积 a * b 可能会超出 64 位整数（long long）的表示范围。为了防止溢出，需要实现一个安全的大数模乘函数。

  • C++: 可以使用 __int128 类型来存储中间结果。
  • Java: 使用 BigInteger 类，它原生支持大数运算。
  • Python: Python 的整数类型原生支持任意精度，无需特殊处理。

关于 Pollard-Pho 算法

虽然题目文件名提到了 Pollard-Pho 算法，但该算法是一种用于质因数分解的算法，而不是用于素性检验。对于本题，米勒-拉宾算法是更直接、更高效的解决方案。

代码

#include <iostream>
#include <vector>

// 使用 __int128 实现大数模乘，防止溢出
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

bool miller_rabin_check(long long d, long long n) {
    long long a = 2 + rand() % (n - 4); // 随机选取基底 a
    long long x = power(a, d, n);

    if (x == 1 || x == n - 1) {
        return true;
    }

    while (d != n - 1) {
        x = (__int128)x * x % n;
        d *= 2;
        if (x == 1) return false;
        if (x == n - 1) return true;
    }
    return false;
}

bool is_prime(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    // 对于 long long 范围内的数，使用一组确定的基底可以获得 100% 准确性
    long long bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    
    long long d = n - 1;
    while (d % 2 == 0) {
        d /= 2;
    }

    for (long long a : bases) {
        if (n == a) return true;
        if (power(a, d, n) != 1) {
            long long t = d;
            bool prime = false;
            while (t < n - 1) {
                if (power(a, t, n) == n - 1) {
                    prime = true;
                    break;
                }
                t *= 2;
            }
            if (!prime) {
                return false;
            }
        }
    }
    return true;
}

void solve() {
    long long n;
    std::cin >> n;
    if (is_prime(n)) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = BigInteger.valueOf(2);

    // 对于 BigInteger, Miller-Rabin 已被封装在 isProbablePrime 方法中
    // 为了演示算法，这里手动实现
    public static boolean isPrime(BigInteger n) {
        if (n.compareTo(TWO) < 0) return false;
        if (n.equals(TWO) || n.equals(BigInteger.valueOf(3))) return true;
        if (n.mod(TWO).equals(ZERO)) return false;
        
        BigInteger d = n.subtract(ONE);
        int s = 0;
        while (d.mod(TWO).equals(ZERO)) {
            d = d.divide(TWO);
            s++;
        }

        long[] bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        
        for (long a_long : bases) {
            BigInteger a = BigInteger.valueOf(a_long);
            if (n.equals(a)) return true;

            BigInteger x = a.modPow(d, n);
            if (x.equals(ONE) || x.equals(n.subtract(ONE))) {
                continue;
            }

            boolean composite = true;
            for (int r = 0; r < s; r++) {
                x = x.modPow(TWO, n);
                if (x.equals(ONE)) {
                    return false; // 找到非平凡平方根, 是合数
                }
                if (x.equals(n.subtract(ONE))) {
                    composite = false;
                    break;
                }
            }
            if (composite) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n_long = sc.nextLong();
            BigInteger n = BigInteger.valueOf(n_long);
            if (isPrime(n)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

import sys

def is_prime(n):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    # 64位整数范围内，这12个基底足够进行确定性判断
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    
    for a in bases:
        if n == a:
            return True
            
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
            
        composite = True
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                composite = False
                break
        
        if composite:
            return False
            
    return True

def solve():
    n = int(sys.stdin.readline())
    if is_prime(n):
        print("Yes")
    else:
        print("No")

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 米勒-拉宾素性检验
  • 时间复杂度: ，其中 是测试用例数， 是选取的基底数量（在此为常数12）。大数模乘和模幂是主要的时间开销。
  • 空间复杂度: