### Python实现：输出小于给定自然数的所有素数列表 以下是一个完整的Python程序，用于输入一个大于2的自然数，并返回所有小于该数的素数列表。 ```python def is_prime(n): """判断一个数是否为素数""" if n <= 1: return False for i in range(2, int(n ** 0.5) + 1): # 检查从2到sqrt(n)的所有整数[^2] if n % i == 0: # 如果n能被i整除，则不是素数 return False return True def find_primes_less_than_n(n): """返回所有小于n的素数列表""" primes = [] for num in range(2, n): # 遍历从2到n-1的所有整数 if is_prime(num): # 如果当前数是素数，则加入结果列表 primes.append(num) return primes # 用户输入 try: user_input = int(input("请输入一个大于2的自然数: ")) if user_input <= 2: print("输入的数字必须大于2。") else: result = find_primes_less_than_n(user_input) print(f"小于 {user_input} 的所有素数为: {result}") except ValueError: print("请输入有效的自然数。") ``` #### 计算上15个台阶楼梯的方法总数 ##### 方法一：递推法 递推法是一种基于动态规划思想的算法，通过逐步计算较小问题的结果来解决较大问题。对于上台阶问题，假设每次可以走1步或2步，则第`n`级台阶的方法总数可以表示为： \[ f(n) = f(n-1) + f(n-2) \] 其中，`f(1) = 1` 和 `f(2) = 2` 是初始条件。 以下是使用递推法的Python代码实现： ```python def climb_stairs_iterative(n): """使用递推法计算上n级台阶的方法总数""" if n == 1: return 1 elif n == 2: return 2 a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b # 更新状态 return b # 输出结果 result_iterative = climb_stairs_iterative(15) print(f"使用递推法计算上15级台阶的方法总数为: {result_iterative}") ``` ##### 方法二：递归法 递归法是一种直接将问题分解为更小子问题的算法。对于上台阶问题，递归公式与递推法相同，但递归方法会重复计算相同的子问题，因此效率较低。以下是使用递归法的Python代码实现： ```python def climb_stairs_recursive(n): """使用递归法计算上n级台阶的方法总数""" if n == 1: return 1 elif n == 2: return 2 return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2) # 输出结果 result_recursive = climb_stairs_recursive(15) print(f"使用递归法计算上15级台阶的方法总数为: {result_recursive}") ``` #### 结果分析 1. **素数列表**： - 程序通过遍历和判断每个数是否为素数，生成了小于给定自然数的所有素数列表。 - 判断素数时，仅需检查到数的平方根即可[^2]。 2. **上台阶方法总数**： - 递推法的时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)，因为只需要存储两个变量。 - 递归法的时间复杂度为 \(O(2^n)\)，空间复杂度为 \(O(n)\)，因为存在大量的重复计算[^1]。 - 在实际应用中，递推法更适合处理大规模问题，而递归法更适合作为问题分析工具[^3]。 ###