自定义函数 `isPrime` 用于判断一个正整数是否为素数，若为素数则返回 `True`，否则返回 `False` [ref_1]。基于此函数，我们可以从 0 到 10000 范围内筛选出所有素数，并获取第 `n` 小的素数。以下是完整的 Python 实现方案。 #### 1. 定义 isPrime 函数 判断素数的核心逻辑是：一个大于1的自然数，如果除了1和它自身外，不能被其他自然数整除，则其为素数 [ref_3]。常见的优化方法是只需检查从2到该数平方根之间的整数即可 [ref_2][ref_5]。 ```python import math def isPrime(num): """ 判断一个正整数是否为素数。 参数: num: 待判断的正整数 返回: True 如果 num 是素数，否则 False """ # 小于等于1的数不是素数 if num <= 1: return False # 2是素数 if num == 2: return True # 大于2的偶数不是素数 if num % 2 == 0: return False # 检查从3到sqrt(num)的奇数 for i in range(3, int(math.sqrt(num)) + 1, 2): if num % i == 0: return False return True ``` #### 2. 筛选 0 到 10000 范围内的素数并获取第 n 小的素数 我们可以通过循环调用 `isPrime` 函数来生成素数列表，然后根据用户输入的 `n` 来获取第 `n` 小的素数 [ref_4]。 ```python def get_nth_prime(n): """ 获取从0到10000范围内第n小的素数。 参数: n: 指定的序号（从1开始计数） 返回: 第n小的素数，如果超出范围则返回None """ prime_list = [] # 遍历0到10000 for number in range(10001): if isPrime(number): prime_list.append(number) # 判断n是否在有效范围内 if 1 <= n <= len(prime_list): return prime_list[n - 1] # 列表索引从0开始 else: return None # 主程序示例 if __name__ == "__main__": try: n = int(input("请输入要获取的第n小的素数（n为正整数）: ")) result = get_nth_prime(n) if result is not None: print(f"在0到10000范围内，第 {n} 小的素数是: {result}") else: print(f"输入的n={n}超出了范围，0到10000范围内共有 {len(prime_list)} 个素数。") except ValueError: print("输入错误，请输入一个正整数。") ``` #### 3. 算法效率分析与优化 上述方法对于范围上限为10000的情况是可行的。然而，如果范围更大，逐个判断的效率会降低。此时可以考虑使用更高效的算法，如**埃拉托斯特尼筛法** [ref_3][ref_6]。 以下是用埃拉托斯特尼筛法实现的版本，它能一次性筛选出指定范围内的所有素数，效率更高。 ```python def sieve_of_eratosthenes(limit): """ 使用埃拉托斯特尼筛法找出0到limit范围内的所有素数。 参数: limit: 范围上限 返回: 一个包含所有素数的列表 """ if limit < 2: return [] # 初始化一个布尔数组，默认所有数都是素数 is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False # 0和1不是素数 # 筛选过程 for i in range(2, int(limit ** 0.5) + 1): if is_prime[i]: # 将i的倍数标记为非素数 for j in range(i * i, limit + 1, i): is_prime[j] = False # 收集所有素数 primes = [num for num, prime in enumerate(is_prime) if prime] return primes def get_nth_prime_optimized(n, limit=10000): """ 使用筛法获取0到limit范围内第n小的素数。 参数: n: 指定的序号 limit: 范围上限，默认为10000 返回: 第n小的素数，如果超出范围则返回None """ primes = sieve_of_eratosthenes(limit) if 1 <= n <= len(primes): return primes[n - 1] else: return None # 使用优化版本 if __name__ == "__main__": try: n = int(input("请输入要获取的第n小的素数（n为正整数）: ")) result = get_nth_prime_optimized(n, 10000) if result is not None: print(f"(使用筛法)在0到10000范围内，第 {n} 小的素数是: {result}") else: all_primes = sieve_of_eratosthenes(10000) print(f"(使用筛法)输入的n={n}超出了范围，0到10000范围内共有 {len(all_primes)} 个素数。") except ValueError: print("输入错误，请输入一个正整数。") ``` #### 4. 两种方法的对比 为了清晰地展示两种实现方式的差异，下表从原理、效率、适用场景等方面进行了对比： | 特性 | 逐个判断法 (`isPrime`循环) | 埃拉托斯特尼筛法 | | :--- | :--- | :--- | | **核心原理** | 对每个数单独进行素性测试 [ref_1][ref_3]。 | 通过标记倍数的方式批量筛除合数 [ref_3][ref_6]。 | | **时间复杂度** | 约为 O(N * √N)，N为范围上限。对于10000，计算量较大。 | 约为 O(N log log N)，效率更高，尤其适合大范围筛选 [ref_6]。 | | **空间复杂度** | O(1) (不存储中间状态) 或 O(P) (存储素数列表)。 | O(N)，需要一个大小为N+1的布尔数组。 | | **优点** | 逻辑直观，无需预知范围，适合单点判断或小范围。 | 一次性生成所有素数，后续查询极快，适合需要多次获取不同位置素数的场景。 | | **缺点** | 范围大时效率低。 | 需要额外的内存空间，且必须预先知道范围上限。 | | **适用场景** | 判断单个或少量数字是否为素数。 | 需要获取一个范围内大量、连续或特定位置的素数 [ref_4]。 | 在本问题中，由于需要获取“第n小的素数”，这意味着我们可能需要多次调用或一次性生成所有素数。因此，**使用埃拉托斯特尼筛法预先计算出0到10000的所有素数并存入列表，是更优的选择**。当用户输入不同的 `n` 时，我们可以直接从列表中通过索引 O(1) 时间复杂度获取结果，响应速度极快 [ref_4]。