使用较快的方法输出1 到N 间的素数。 输入格式: 输入一个正整数n。(1<n<=1000000) 输出格式: 输出小于等于n的所有素数，每个素数以空格隔开 用多种方法的c语言完成

除了埃氏筛法，还有其他一些方法可以用来寻找素数。下面介绍两种常用的算法：线性筛法和欧拉筛法。

### 线性筛法

线性筛法是对埃氏筛法的一种优化。埃氏筛法的时间复杂度是 $O(n\log\log n)$，主要瓶颈在于重复标记合数的操作。线性筛法通过记录每个合数的最小质因子，避免了重复标记的问题，从而将时间复杂度降低到 $O(n)$。

以下是使用线性筛法寻找小于等于 n 的所有素数的 C 代码实现：

#include <stdio.h>
#include <stdlib.h>

void find_primes(int n) {
    int *primes = (int*) malloc((n+1) * sizeof(int)); // 动态分配数组空间
    int *is_prime = (int*) malloc((n+1) * sizeof(int)); // 动态分配数组空间
    int cnt = 0;
    int i, j;
    for (i = 2; i <= n; i++) {
        if (is_prime[i] == 0) {
            primes[cnt++] = i; // 将素数保存到数组中
        }
        for (j = 0; j < cnt && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = 1; // 标记合数的最小质因子
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    for (i = 0; i < cnt; i++) {
        printf("%d ", primes[i]); // 输出素数
    }
    free(primes);
    free(is_prime);
}

int main() {
    int n;
    scanf("%d", &n);
    find_primes(n);
    return 0;
}

该算法的思路是从小到大枚举每个数 i，如果 i 是素数，则将其加入素数数组中，并将其所有的倍数标记为合数的最小质因子；如果 i 不是素数，则将其标记为合数的最小质因子，但不需要再将其所有的倍数标记为合数了。这样一来，每个合数只会被标记一次，因此时间复杂度为 $O(n)$。

### 欧拉筛法

欧拉筛法是线性筛法的另一种优化。线性筛法的主要瓶颈在于每个合数都会被它的最小质因子标记一次，而欧拉筛法通过对每个数只使用它的最小质因子来避免这个问题，从而进一步提高了时间效率。

以下是使用欧拉筛法寻找小于等于 n 的所有素数的 C 代码实现：

#include <stdio.h>
#include <stdlib.h>

void find_primes(int n) {
    int *primes = (int*) malloc((n+1) * sizeof(int)); // 动态分配数组空间
    int *is_prime = (int*) malloc((n+1) * sizeof(int)); // 动态分配数组空间
    int cnt = 0;
    int i, j;
    for (i = 2; i <= n; i++) {
        if (is_prime[i] == 0) {
            primes[cnt++] = i; // 将素数保存到数组中
        }
        for (j = 0; j < cnt && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = 1; // 标记合数
            if (i % primes[j] == 0) {
                break; // 如果 i 的最小质因子是 primes[j]，则不需要再考虑 i * primes[j] 了
            }
        }
    }
    for (i = 0; i < cnt; i++) {
        printf("%d ", primes[i]); // 输出素数
    }
    free(primes);
    free(is_prime);
}

int main() {
    int n;
    scanf("%d", &n);
    find_primes(n);
    return 0;
}

该算法的思路与线性筛法类似，不同之处在于每个数只使用了它的最小质因子，而不是所有的质因子。因此，每个合数最多只会被标记一次，时间复杂度是 $O(n)$。