掌握三种方法，判断正整数质数不再难——Python练习

在Python编程语言中，判断一个正整数是否为质数是初学者经常遇到的一个基础练习题。质数（Prime number）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。判断质数的方法有很多种，以下是三种常见的实现方法，它们分别是： 1. 循环判断法 这是最直观也是最基础的方法，通过循环遍历从2到这个正整数的平方根的所有整数，来检查这个数是否有除了1和它本身以外的因数。如果在这个范围内找到一个数可以整除这个正整数，则说明它不是质数；如果遍历完都没有找到，则说明它是质数。这种方法的时间复杂度为O(sqrt(n))，其中n是要判断的正整数。 2. 优化判断法 优化判断法是循环判断法的一种改进，它通过减少循环的次数来提高效率。由于任何合数（非质数）都可以表示为两个质数的乘积，且这两个质数中必有一个小于或等于该合数的平方根，所以我们在循环判断时只需要检查到这个正整数的平方根即可。然而，我们还可以进一步优化，只需要检查到sqrt(n)即可，因为如果n是合数，那么它至少有一个因数小于或等于sqrt(n)。这种方法同样具有O(sqrt(n))的时间复杂度。 3. 埃拉托斯特尼筛法（Sieve of Eratosthenes） 这是一种更为高效的算法，适用于判断一个较小范围内的所有数是否为质数。它的工作原理是：首先创建一个列表，列表中索引代表数值，列表值的真假代表该索引是否为质数。算法从最小的质数2开始，将所有2的倍数在列表中标记为非质数，接着找到下一个未被标记的数，重复上述操作，直到列表中所有小于或等于sqrt(n)的索引都被处理。这个方法的一个优点是它不仅可以判断单个数是否为质数，还可以获取指定范围内所有质数的列表。 下面通过Python代码具体展示这三种方法： ```python import math # 方法1：循环判断法 def is_prime_loop(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True # 方法2：优化判断法 def is_prime_optimized(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True # 方法3：埃拉托斯特尼筛法 def sieve_of_eratosthenes(limit): primes = [] sieve = [True] * (limit + 1) for num in range(2, int(math.sqrt(limit)) + 1): if sieve[num]: primes.append(num) for multiple in range(num*num, limit+1, num): sieve[multiple] = False for num in range(int(math.sqrt(limit)) + 1, limit + 1): if sieve[num]: primes.append(num) return primes # 测试代码 print(is_prime_loop(11)) # 输出: True print(is_prime_optimized(11)) # 输出: True print(sieve_of_eratosthenes(50)) # 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] ``` 在这段代码中，我们定义了三个函数来实现这三种方法。循环判断法和优化判断法只需要一行调用即可返回结果，而埃拉托斯特尼筛法则返回了一个列表，其中包含了所有小于或等于设定上限的质数。 总结来说，判断一个正整数是否为质数是学习Python时经常会遇到的练习题，它不仅有助于理解基础的数值运算，还可以帮助初学者掌握Python的基本语法和逻辑。三种方法各有优劣，初学者可以根据需要判断的数的大小和范围选择合适的方法。