Python 实现：求 n 以内最大 k 个素数及其和，附代码详解与复杂度分析

以下是使用 Python 实现该功能的代码： ```python # 判断一个数是否为素数 def is_prime(num): if num < 2: return False for i in range(2, int(num 0.5) + 1): if num % i == 0: return False return True # 获取输入 n, k = map(int, input().split()) # 存储找到的素数 primes = [] # 从 n 开始递减遍历，找到最大的 k 个素数 for i in range(n, 1, -1): if is_prime(i): primes.append(i) if len(primes) == k: break # 计算素数的总和 total = sum(primes) # 输出结果 prime_str = "+".join(map(str, primes)) print(f"{prime_str}={total}") ``` 代码解释 1. `is_prime` 函数：用于判断一个数是否为素数。如果该数小于 2，则不是素数；否则，检查从 2 到该数的平方根的所有数是否能整除该数，如果能整除，则不是素数。 2. 获取输入：使用 `input().split()` 获取用户输入的 `n` 和 `k`，并使用 `map(int, ...)` 将其转换为整数。 3. 找到最大的 k 个素数：从 `n` 开始递减遍历，调用 `is_prime` 函数判断每个数是否为素数，如果是素数，则将其添加到 `primes` 列表中。当 `primes` 列表的长度达到 `k` 时，停止遍历。 4. 计算总和：使用 `sum(primes)` 计算 `primes` 列表中所有素数的总和。 5. 输出结果：使用 `"+".join(map(str, primes))` 将 `primes` 列表中的素数转换为字符串，并用 `+` 连接起来，然后输出结果。 复杂度分析 - 时间复杂度：$O(n\sqrt{n})$，其中 $n$ 是输入的上限。主要是因为需要遍历从 $n$ 到 2 的所有数，并对每个数进行素数判断。 - 空间复杂度：$O(k)$，其中 $k$ 是需要找到的素数的个数。主要是因为需要存储找到的素数。 ######[AI问答 | 561点数解答 | 2025-12-10 22:55:16]