素数判断算法：从基础试除法到米勒-拉宾测试

1. 素数判断的基本概念与数学原理

素数是数学中最基础也最重要的概念之一，指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。比如2、3、5、7都是素数，而4、6、8、9则不是。素数判断看似简单，但在密码学、计算机科学等领域有着广泛应用。

判断素数的核心在于验证该数是否能被其他数整除。最直观的方法是试除法：对于一个待测数n，检查从2到n-1的所有整数是否能整除n。如果存在能整除n的数，则n不是素数；否则n是素数。

注意：1不是素数也不是合数，这是个特殊约定。所有素数判断算法都应首先排除n=1的情况。

2. 基础算法实现与优化思路

2.1 朴素试除法实现

最基础的素数判断算法可以这样实现：

python复制def is_prime_naive(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

这个算法的时间复杂度是O(n)，对于大数来说效率很低。我们可以进行几个关键优化：

1. 只需检查到√n：如果n是合数，那么它至少有一个因数小于等于√n
2. 跳过偶数：除了2，所有偶数都不是素数
3. 提前终止：一旦发现一个因数就可以立即返回False

2.2 优化后的试除法

python复制def is_prime_optimized(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

这个优化版本的时间复杂度降到了O(√n)，效率提升显著。对于n=1,000,000，朴素算法需要约100万次运算，而优化版只需约1000次。

3. 更高效的素数判断算法

3.1 米勒-拉宾素性测试

对于