Python查找质数

### 查找质数的Python实现 质数是指大于1的自然数中，除了1和它本身以外不再有其他因数的数。以下是通过Python编写的查找质数的程序： #### 方法一：暴力法 此方法遍历从2到n-1的所有整数来判断是否存在因子。 ```python def is_prime_v1(n): if n <= 1: return False for i in range(2, n): # 遍历可能的因子 if n % i == 0: # 如果存在因子，则不是质数 return False return True # 否则返回True表示是质数[^1] # 测试函数 for num in range(2, 20): if is_prime_v1(num): print(f"{num} 是质数") ``` 这种方法的时间复杂度较高，为O(n²)，因此对于较大的数值效率较低。 --- #### 方法二：优化后的暴力法 由于如果一个数n可以被分解成两个因数相乘的形式 (i * j = n)，那么至少有一个因数小于等于sqrt(n)。所以只需检查从2到√n之间的所有整数即可。 ```python import math def is_prime_v2(n): if n <= 1: return False sqrt_n = int(math.sqrt(n)) + 1 for i in range(2, sqrt_n): # 只需检查至平方根范围内的数 if n % i == 0: return False return True # 若无任何因子，则该数为质数[^1] # 测试函数 for num in range(2, 50): if is_prime_v2(num): print(f"{num} 是质数") ``` 时间复杂度降低到了 O(sqrt(n))，适合处理更大的数据集。 --- #### 方法三：埃拉托斯特尼筛法（Sieve of Eratosthenes） 这是一种高效的寻找一定范围内所有质数的方法。其基本思想是从最小的质数2开始，将它的倍数标记为合数；接着找到下一个未被标记的数作为新的质数，并重复这一过程直到结束。 ```python def sieve_of_eratosthenes(limit): primes = [] sieve = [True] * (limit + 1) sieve[0], sieve[1] = False, False for current_number in range(2, limit + 1): if sieve[current_number]: primes.append(current_number) # 将当前数加入质数列表 for multiple in range(current_number*2, limit + 1, current_number): sieve[multiple] = False # 标记当前数的倍数为非质数 return primes # 找出指定范围内的所有质数 print(sieve_of_eratosthenes(100)) ``` 这种算法适用于快速筛选大量连续整数中的质数，尤其当目标区间较大时表现优异。 --- ### 总结 以上提供了三种不同的方式用于检测单个数字是否为质数以及生成一系列质数。每种方法都有各自的适用场景，在实际应用过程中可以根据具体需求选择合适的技术方案。