Python实现素数对查找算法及性能优化

我来帮你编写找出所有素数对的程序。这是一个寻找孪生素数的问题。 ```python def is_prime(n): """判断一个数是否为素数""" if n < 2: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True def find_prime_pairs(x): """找出所有小于等于x的素数对""" # 生成所有小于等于x的素数列表 primes = [] for i in range(2, x + 1): if is_prime(i): primes.append(i) # 查找相差为2的素数对 prime_pairs = [] for i in range(len(primes) - 1): if primes[i+1] - primes[i] == 2: prime_pairs.append((primes[i], primes[i+1])) return prime_pairs # 读取输入 x = int(input()) # 查找并输出素数对 pairs = find_prime_pairs(x) for pair in pairs: print(pair[0], pair[1]) ``` **代码说明：** ### 🔍 核心算法 - `is_prime()` 函数判断一个数是否为素数 - 使用平方根优化，只检查到 √n 即可 ### 📊 执行流程 1. 生成 [2, x] 范围内的所有素数 2. 遍历素数列表，找出相差为2的相邻素数对 3. 按顺序输出所有素数对 ### ⚡ 时间复杂度 - 生成素数：O(n√n) - 查找素数对：O(n) - 整体效率可以满足题目要求 **测试样例：** 输入 `100` 将输出： ``` 3 5 5 7 11 13 17 19 29 31 41 43 59 61 71 73 ``` ######[AI问答 | 436点数解答 | 2026-07-07 23:20:04]