设计一个c语言程序，输出所有小于等于n的素数。并分析该算法的时间复杂度

设计一个 C 语言程序，用于输出所有小于等于给定整数 n 的素数，可以使用著名的“埃拉托斯特尼筛法”（Sieve of Eratosthenes）。以下是简单的代码实现：

#include <stdio.h>

// 判断是否为素数的函数
int is_prime(int num) {
    if (num <= 1)
        return 0;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

// 输出所有小于等于n的素数
void print_primes(int n) {
    // 创建一个布尔数组，初始假设从2到n的所有数都是素数
    int prime[n + 1];
    memset(prime, 1, sizeof(prime));

    for (int p = 2; p * p <= n; p++) {
        // 如果prime[p]还未被标记为非素数，则它是素数
        if (prime[p]) {
            // 标记p的倍数为非素数
            for (int i = p * p; i <= n; i += p)
                prime[i] = 0;
        }
    }

    printf("素数：");
    for (int p = 2; p <= n; p++)
        if (prime[p])
            printf("%d ", p);
}

int main() {
    int n;
    printf("请输入一个正整数 n：");
    scanf("%d", &n);

    print_primes(n);
    return 0;
}

时间复杂度分析：
- 在`is_prime`函数中，我们遍历了从2到√n，所以循环次数大约为n/2，这是一个线性的操作，时间复杂度是O(n/2)，即O(n)。
- 主函数中，我们执行了一次埃拉托斯特尼筛法，对于每个素数p，我们将它的倍数标记为合数，这需要O(n/p)次操作。由于我们只对不超过n的数做这个操作，所以总的开销为所有p（2到√n）的和，约为(1+2+...+√n)，这是一个等差数列求和，近似于√n * √n / 2，也即O(n)。

综上所述，整个程序的时间复杂度主要由第一个循环决定，整体时间复杂度是O(n)。这是因为在最坏的情况下，我们需要检查所有的n个数字来确定它们是否是素数。