素数判断算法：从基础试除法到优化实现

1. 素数的定义与基本概念

素数（Prime Number）是指大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。换句话说，素数只有两个正因数：1和它本身。这个概念在数学中有着极其重要的地位，从古希腊数学家欧几里得开始，素数就一直是数论研究的核心对象。

理解素数的关键在于把握它的两个基本特征：首先，素数必须是大于1的自然数；其次，它的因数只能是1和它本身。比如2、3、5、7、11等都是典型的素数，而4、6、8、9等则不是素数（称为合数）。特别需要注意的是，1既不是素数也不是合数，这是一个常见的误解点。

在实际应用中，素数有着广泛的用途。在密码学领域，大素数的乘积被用于RSA加密算法；在计算机科学中，素数被用于哈希表的设计；在数学研究中，素数分布规律更是数论的核心课题之一。因此，掌握判断素数的方法不仅是一个编程练习，更是理解这些高级应用的基础。

2. 判断素数的基本方法

2.1 试除法原理

试除法是最直观的判断素数的方法。其基本思路是：对于一个待判断的数n，尝试用2到n-1之间的所有整数去除n，如果都不能整除，则n是素数；否则，n是合数。这种方法直接体现了素数的定义，易于理解和实现。

从数学角度看，试除法的正确性基于以下事实：如果n是合数，那么它至少有一个因数小于或等于√n。这意味着我们实际上只需要检查2到√n之间的整数是否能整除n即可，这可以显著减少计算量。例如，判断101是否为素数，我们只需要检查2到10（因为√101≈10.05）之间的整数是否能整除101，而不需要检查到100。

2.2 基础实现代码

以下是一个使用Python实现的试除法判断素数的函数：

python复制def is_prime(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

这个实现包含了几个优化点：

1. 首先排除了小于等于1的