Python函数怎样写一个判断是否为质数的函数 Python函数质数判断的入门编写教程​

判断一个数是否为质数只需检查到其平方根，因为若n有大于√n的因数，则必有对应的小于√n的因数；1. 处理边界情况：n≤1非质数，n=2是质数，大于2的偶数非质数；2. 对奇数从3开始以步长2检查至√n+1，若存在整除则非质数；3. 未找到因数则为质数；此方法时间复杂度为o(√n)，适用于单个数判断，而大数或批量判断可采用miller-rabin测试或埃拉托斯特尼筛法优化。

判断一个数是不是质数，在Python里写个函数其实并不复杂，核心就是检查它除了1和自身之外，有没有别的因数。简单来说，如果一个大于1的自然数，除了1和它本身，不能被其他任何自然数整除，那它就是质数。写函数时，我们通常会优化一下，比如只检查到这个数的平方根，这样效率会高很多。

解决方案

import math

def is_prime(n):
    """
    判断一个正整数是否为质数。

    质数是大于1的自然数，除了1和它本身，不能被其他任何自然数整除。

    参数:
        n (int): 需要判断的整数。

    返回:
        bool: 如果n是质数则返回True，否则返回False。
    """
    # 质数定义：必须大于1
    if n <= 1:
        return False
    # 2是最小的质数，也是唯一的偶数质数
    if n == 2:
        return True
    # 所有大于2的偶数都不是质数
    if n % 2 == 0:
        return False

    # 从3开始，只检查奇数，直到sqrt(n)
    # 因为如果n有一个大于sqrt(n)的因数，那么它必然有一个小于sqrt(n)的因数。
    # 所以我们只需要检查到sqrt(n)即可。
    # 步长为2，跳过偶数，因为偶数已经排除了。
    limit = int(math.sqrt(n)) + 1
    for i in range(3, limit, 2):
        if n % i == 0:
            return False # 找到了因数，不是质数

    return True # 没有找到因数，是质数

# 示例调用
# print(is_prime(7))   # True
# print(is_prime(10))  # False
# print(is_prime(1))   # False
# print(is_prime(2))   # True
# print(is_prime(97))  # True
# print(is_prime(99))  # False

这段代码的核心思路是：先处理那些特殊的边界情况，比如小于等于1的数肯定不是质数，2是质数，所有大于2的偶数都不是质数。然后，对于剩下的奇数，我们只需要从3开始，以2为步长（也就是只检查奇数），一直检查到这个数的平方根。如果在这个范围内找到了任何一个能整除它的数，那它就不是质数。如果循环结束了都没找到，恭喜，它就是个质数。我个人觉得，这种优化是编写质数判断函数时最基础也最实用的技巧，能避免很多不必要的计算。

为什么在Python中判断质数时，只需要检查到其平方根？

这其实是个数学上的小巧妙，但对程序性能的影响可不小。我们来想想看：如果一个数

n

a

n = a * b

a

b

n

立即学习“Python免费学习笔记（深入）”；

现在关键点来了：如果

a

b

sqrt(n)

a * b

sqrt(n) * sqrt(n)

n

n = a * b

a

sqrt(n)

这就意味着，我们没必要傻乎乎地从2一直检查到

n-1

sqrt(n)

sqrt(n)

O(n)

O(sqrt(n))

在实际应用中，质数判断函数有哪些常见的误区和优化考量？

写质数判断函数，虽然看似简单，但实际操作中还是有些地方容易犯错或者可以进一步优化：

一个很常见的误区就是边界条件处理不当。比如，忘了处理

n=1

n=2

1

2

range(3, int(math.sqrt(n)))

sqrt(n)

int(math.sqrt(n)) + 1

Bika.ai

打造您的AI智能体员工团队

下载

关于性能，特别是对于极大数，我们上面讨论的

O(sqrt(n))

sqrt(n)

此外，如果你的应用场景是需要判断大量连续的数字是否为质数（比如找出1到1000000之间的所有质数），那么每次都调用

is_prime

除了判断单个质数，还有哪些相关的质数算法和概念值得学习？

质数的世界远比我们想象的要广阔和有趣，它不只是一个简单的“是或否”判断。

首先，埃拉托斯特尼筛法绝对值得深入学习。前面提到了，它不是用来判断单个质数的，而是用来“筛选”一定范围内所有质数的。它的基本思想是：从2开始，把2的倍数都标记为非质数；然后找到下一个未被标记的数（也就是3），把3的倍数都标记为非质数，以此类推。这种“筛”的方式效率极高，是处理质数序列问题的基石。

其次，质因数分解也是一个非常重要的概念和算法。任何一个大于1的合数都可以唯一地表示成若干个质数的乘积，这就是算术基本定理。将一个大数分解成它的质因数，在密码学中有着核心地位，因为很多加密算法的安全性都建立在“大数质因数分解极其困难”这一假设之上。虽然目前没有非常高效的通用质因数分解算法，但了解其原理和一些基础的分解方法（比如试除法、Pollard's rho算法等）是很有益的。

再往深了看，你会遇到一些更抽象但同样迷人的概念，比如同余理论，它是数论的一个分支，很多质数相关的算法和定理都建立在其上。还有一些特殊的质数类型，像梅森质数（Mersenne Prime），它是形如

2^p - 1

这些概念和算法，有些直接提升我们程序的效率，有些则揭示了数论的深邃和美妙，都是探索质数世界不可或缺的部分。