用python编写程序，输入一个大于2 的自然数，然后输出小于该数字的所有素数组成的列表。 要求采用两种方法求解。

方法一：暴力枚举法

代码如下：

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

n = int(input("请输入一个大于2的自然数："))
primes = []
for i in range(2, n):
    if is_prime(i):
        primes.append(i)

print(primes)

方法二：埃氏筛法

代码如下：

n = int(input("请输入一个大于2的自然数："))
is_prime = [True] * n
for i in range(2, int(n ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, n, i):
            is_prime[j] = False

primes = [i for i in range(2, n) if is_prime[i]]
print(primes)

两种方法的时间复杂度都是 O(nloglogn)，但是埃氏筛法的空间复杂度更小，因为只需要一个长度为 n 的布尔数组，而暴力枚举法需要一个长度为素数个数的列表。

相关问题

用python编写一个程序输入一个大于2的自然数，然后输出小于该数字的所有素数组成的列表

当然可以。下面是一个简单的Python程序，它会提示用户输入一个大于2的自然数，然后找出所有小于这个数的质数并打印出来：

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def prime_factors_below(n):
    primes = []
    for num in range(2, n):
        if is_prime(num):
            primes.append(num)
    return primes

n = int(input("请输入一个大于2的自然数: "))
if n > 2:
    prime_list = prime_factors_below(n)
    print(f"小于{n}的所有素数有: {prime_list}")
else:
    print("输入的数值需要大于2。")

编写程序输入一个大于2的自然数，输出小于该数字所有素数组成的列表

编写一个程序来生成小于给定自然数的所有素数列表，你可以采用埃拉托斯特尼筛法（Sieve of Eratosthenes），这是一种高效找出一定范围内所有质数的经典算法。以下是Python代码示例：

def sieve_of_eratosthenes(n):
    primes = [True] * (n+1)  # 初始化一个布尔列表表示所有数字都是质数
    p = 2
    while p**2 <= n:
        if primes[p]:  # 如果p是质数
            for i in range(p**2, n+1, p):  # 将p的倍数标记为合数
                primes[i] = False
        p += 1
    prime_numbers = [i for i in range(2, n) if primes[i]]  # 获取质数列表
    return prime_numbers

# 输入值
input_number = int(input("请输入一个大于2的自然数: "))

# 输出小于输入数字的素数列表
prime_list = sieve_of_eratosthenes(input_number)
print(f"小于{input_number}的所有素数是: {prime_list}")