判断一个数是否为质数只需检查到其平方根，因为若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不是质数，那它肯定能被除了1和它自身以外的某个数
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))，对于大数来说，效率提升是指数级的。比如判断100万是不是质数，检查到999999和检查到1000，这简直是天壤之别。
在实际应用中，质数判断函数有哪些常见的误区和优化考量？
写质数判断函数，虽然看似简单，但实际操作中还是有些地方容易犯错或者可以进一步优化：
一个很常见的误区就是边界条件处理不当。比如，忘了处理
n=1的情况，或者把
n=2也纳入到循环判断中。
1既不是质数也不是合数，而
2是最小且唯一的偶数质数，它们都需要单独拎出来处理，否则逻辑会混乱。另一个小坑是循环范围的设定，比如
range(3, int(math.sqrt(n)))这种，很容易导致漏掉
sqrt(n)那个点，虽然概率小，但理论上还是可能出问题，所以通常会写成
int(math.sqrt(n)) + 1，确保包含边界。
关于性能，特别是对于极大数，我们上面讨论的
O(sqrt(n))优化已经很不错了。但如果我们要判断一个有几百位、几千位的大数是不是质数，
sqrt(n)依然是个天文数字。这时候，我们就不能用这种确定性的试除法了。业界通常会转向概率性测试，比如Miller-Rabin素性测试。它不是100%确定，但可以通过多次测试将出错的概率降到极低，几乎可以忽略不计。这种算法在密码学里非常重要，像RSA加密就大量依赖于大质数的生成和判断。
此外，如果你的应用场景是需要判断大量连续的数字是否为质数（比如找出1到1000000之间的所有质数），那么每次都调用
is_prime函数会显得效率低下。这时候，埃拉托斯特尼筛法（Sieve of Eratosthenes）就派上用场了。它是一种非常高效的批量生成质数的方法，通过标记和排除合数，能在一个合理的时间内找出指定范围内的所有质数。这和我们判断单个质数的思路完全不同，但却是另一个非常重要的工具。
除了判断单个质数，还有哪些相关的质数算法和概念值得学习？
质数的世界远比我们想象的要广阔和有趣，它不只是一个简单的“是或否”判断。
首先，埃拉托斯特尼筛法绝对值得深入学习。前面提到了，它不是用来判断单个质数的，而是用来“筛选”一定范围内所有质数的。它的基本思想是：从2开始，把2的倍数都标记为非质数；然后找到下一个未被标记的数（也就是3），把3的倍数都标记为非质数，以此类推。这种“筛”的方式效率极高，是处理质数序列问题的基石。
其次，质因数分解也是一个非常重要的概念和算法。任何一个大于1的合数都可以唯一地表示成若干个质数的乘积，这就是算术基本定理。将一个大数分解成它的质因数，在密码学中有着核心地位，因为很多加密算法的安全性都建立在“大数质因数分解极其困难”这一假设之上。虽然目前没有非常高效的通用质因数分解算法，但了解其原理和一些基础的分解方法（比如试除法、Pollard's rho算法等）是很有益的。
再往深了看，你会遇到一些更抽象但同样迷人的概念，比如同余理论，它是数论的一个分支，很多质数相关的算法和定理都建立在其上。还有一些特殊的质数类型，像梅森质数（Mersenne Prime），它是形如
2^p - 1的质数，很多最大的已知质数都是梅森质数；以及孪生质数（Twin Primes），指相差为2的两个质数（如3和5，11和13），关于它们是否存在无限对，至今仍是未解之谜。
这些概念和算法，有些直接提升我们程序的效率，有些则揭示了数论的深邃和美妙，都是探索质数世界不可或缺的部分。
