### Python 实现获取 1 到 n 之间所有质数的算法 以下是几种常见的方法来实现这一功能： #### 方法一：暴力枚举法 这种方法通过逐一检查每个数字是否为质数来进行筛选。虽然简单易懂，但在处理较大范围时效率较低。 ```python def find_primes_brute_force(n): primes = [] for num in range(2, n + 1): # 质数从2开始 is_prime = True for divisor in range(2, num): # 验证是否存在因子 if num % divisor == 0: is_prime = False break if is_prime: primes.append(num) return primes ``` 此方法的时间复杂度接近 \(O(n^2)\)，因为对于每个数字都需要进行多次除法操作[^1]。 --- #### 方法二：优化后的试除法 为了提高性能，可以减少不必要的计算。例如，只需验证到 \(\sqrt{n}\) 即可，因为如果一个数有因数大于其平方根，则必然有一个对应的较小因数。 ```python import math def find_primes_optimized_trial_division(n): primes = [] for num in range(2, n + 1): is_prime = True sqrt_num = int(math.sqrt(num)) + 1 for divisor in range(2, sqrt_num): if num % divisor == 0: is_prime = False break if is_prime: primes.append(num) return primes ``` 该方法显著降低了时间复杂度至大约 \(O(n\sqrt{n})\)，适合中小规模的数据集[^3]。 --- #### 方法三：埃拉托色尼筛法（Sieve of Eratosthenes） 这是一种经典的高效算法，用于快速找出一定范围内所有的质数。它的核心思想是从最小的质数开始逐步标记合数。 ```python def sieve_of_eratosthenes(n): if n < 2: return [] is_prime = [True] * (n + 1) # 初始化布尔数组，默认全部设为真 is_prime[0], is_prime[1] = False, False # 0 和 1 不是质数 for i in range(2, int(math.sqrt(n)) + 1): if is_prime[i]: for multiple in range(i * i, n + 1, i): # 将倍数标记为假 is_prime[multiple] = False primes = [num for num, status in enumerate(is_prime) if status] return primes ``` 这种算法的时间复杂度约为 \(O(n \log{\log{n}})\)，非常适合大规模数据的场景[^4]。 --- #### 方法四：线性筛法（欧拉筛法） 相比埃拉托色尼筛法，线性筛法进一步减少了重复标记的操作次数，从而达到真正的线性时间复杂度 \(O(n)\)。 ```python def linear_sieve(n): if n < 2: return [] primes = [] # 存储找到的质数 is_prime = [True] * (n + 1) # 布尔数组初始化 is_prime[0], is_prime[1] = False, False for i in range(2, n + 1): if is_prime[i]: primes.append(i) for prime in primes: if i * prime > n: break is_prime[i * prime] = False if i % prime == 0: # 关键条件，避免重复标记 break return primes ``` 这种方法特别适用于需要频繁查询的情况，因为它能够一次性构建完整的质数列表[^3]。 --- ### 总结 以上四种方法各有优劣： - **暴力枚举法**易于理解但效率低下。 - **优化后的试除法**适合作为入门级改进方案。 - **埃拉托色尼筛法**提供了较好的平衡，在大多数情况下表现优异。 - **线性筛法**则是在追求极致性能时的最佳选择。 最终推荐使用埃拉托色尼筛法或线性筛法作为实际应用中的首选解决方案。 ---