Python素数判定全解析（从零开始掌握素数判断算法）

方法一：基础暴力法

最直观的方法是从2开始，逐个检查到 n-1，看是否有能整除 n 的数。如果有，则不是素数；否则是素数。

def is_prime_basic(n):    if n < 2:        return False    for i in range(2, n):        if n % i == 0:            return False    return True# 测试print(is_prime_basic(7))   # 输出: Trueprint(is_prime_basic(10))  # 输出: False  

这个方法简单易懂，适合初学者学Python时理解循环和条件判断。但它的效率较低，尤其当 n 很大时，会非常慢。

方法二：优化版——只检查到√n

数学上可以证明：如果一个数 n 有因数，那么至少有一个因数 ≤ √n。因此我们只需检查从2到√n之间的整数即可。

import mathdef is_prime_optimized(n):    if n < 2:        return False    if n == 2:        return True    if n % 2 == 0:        return False  # 排除所有偶数        # 只检查奇数，从3到√n    for i in range(3, int(math.sqrt(n)) + 1, 2):        if n % i == 0:            return False    return True# 测试print(is_prime_optimized(29))  # 输出: Trueprint(is_prime_optimized(100)) # 输出: False  

这个版本大大减少了循环次数，时间复杂度从 O(n) 降到了 O(√n)，是实际开发中常用的素数算法。

方法三：埃拉托斯特尼筛法（批量生成素数）

如果你需要找出小于某个数的所有素数（比如找100以内的所有素数），使用“筛法”更高效。

def sieve_of_eratosthenes(limit):    is_prime = [True] * (limit + 1)    is_prime[0] = is_prime[1] = False  # 0和1不是素数        for i in range(2, int(limit**0.5) + 1):        if is_prime[i]:            for j in range(i*i, limit + 1, i):                is_prime[j] = False        return [num for num, prime in enumerate(is_prime) if prime]# 找出100以内的所有素数primes = sieve_of_eratosthenes(100)print(primes)  

总结

通过本教程，你已经掌握了三种不同的Python素数判定方法：

• 基础暴力法：适合理解逻辑
• 优化判定法：适合单个数字快速判断
• 埃拉托斯特尼筛法：适合批量生成素数

无论你是刚开始接触初学者学Python，还是想巩固算法基础，这些方法都能帮助你更好地理解编程与数学的结合。快动手试试吧！

关键词回顾：Python素数判定、素数算法、Python编程教程、初学者学Python。