试除法原理详解

什么是试除法

简单来说就是按照质数的概念来的。 质数是指大于1的自然数，除了1和它本身之外没有其他因数。 试除法是最直观的质数判断方法，其核心思想是检查给定的数n是否能被2到n-1之间的任何数整除。如果能被整除，则不是质数；否则是质数。

但是n如果太大，这个算法就太慢了，怎么优化？

试除法的数学基础

试除法源于数论中的因数对称性原理：对于任意整数n，若存在因数d，则必定存在对应的因数n/d。这两个因数满足d ≤ n/d ⇒ d² ≤ n ⇒ d ≤ √n

这一性质使得我们只需检查2到√n范围内的整数即可确定n的质性，将时间复杂度从O(n)优化到O(√n)

关键优化步骤证明

1. 范围优化：

   假设存在因数d > √n，则对应因数n/d < √n
   因此只需检查较小因数即可
   

2. 奇偶优化：

   ∀n>2，若n为偶数则必非质数
   检查2后，后续只需检查奇数：
   试除次数 = ⎡√n/2⎤ → 减少50%运算量
   

3. 提前终止：

   for i in range(3, sqrt(n)+1, 2):
       if n % i == 0:  # 发现第一个因数即可终止
           return False
   

复杂度对比

算法演进图示

原始试除法 → 平方根优化 → 奇偶优化 → 预筛法优化
            ↓
Miller-Rabin测试（处理更大数字）

扩展优化思路

1. 预筛法：先检查2、3、5的倍数，减少循环次数
2. 6k±1定理：所有质数（除2、3）都形如6k±1
3. 概率测试：结合费马测试处理超大数据（>1e18）

// 6k±1优化版本示例
bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2==0 || n%3==0) return false;
  
    // 检查6k±1形式的数
    for(long long i=5; i*i<=n; i+=6){
        if(n%i==0 || n%(i+2)==0)
            return false;
    }
    return true;
}

数学证明补充

定理：若n是合数，则必有质因数≤√n 证明： 设n = a×b，假设a > √n且b > √n → a×b > n，矛盾 故至少有一个因数≤√n

实际性能测试

当n=999999999989（大质数）时：

• 原始试除法：约1万亿次运算 → 不可行
• 优化试除法：约5e5次运算 → <1ms完成

此优化使得算法能处理题目要求的1e12量级数据，在编程竞赛中既能保证正确性又符合时间限制要求。