数据结构与算法设计一个程序，输出所有小于等于 n 的素数，并分析该算法的时间复杂度

数据结构和算法设计通常会涉及到高效的查找和处理整数集合的能力。为了输出所有小于等于给定整数 n 的素数，我们可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一种常见的求素数序列的经典算法。

以下是使用 Python 实现的一个简单版本：

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)  # 初始化一个布尔数组，所有元素均为 True
    p = 2
    while p * p <= n:
        if primes[p]:  # 如果 p 是素数
            for i in range(p * p, n + 1, p):  # 将 p 的倍数标记为非素数
                primes[i] = False
        p += 1

    # 输出所有的素数
    prime_numbers = [p for p in range(2, n + 1) if primes[p]]
    return prime_numbers

# 测试
n = int(input("请输入一个正整数: "))
prime_list = sieve_of_eratosthenes(n)
print(f"小于等于 {n} 的所有素数是: {prime_list}")

时间复杂度分析：
- 筛法的主要操作是在循环中将每个素数的倍数设置为非素数。这个过程需要遍历从 2 到 sqrt(n)，所以主循环大约进行了 O(sqrt(n)) 次操作。
- 遍历整个数组并输出素数的时间可以忽略，因为总共有 n 个元素，但在大多数情况下这远小于 O(sqrt(n))。
- 因此，埃拉托斯特尼筛法的整体时间复杂度是 O(n log log n)，其中 log log n 是因式分解导致的操作次数。