详细讲讲素数的埃氏筛法，C语言

素数埃拉托斯特尼筛法（Sieve of Eratosthenes），也叫埃氏筛，是一种古老的计算求解小于一定范围内的所有质数的经典算法。以下是C语言版本的基本步骤：

1. 创建一个大小为n+1的布尔数组isPrime[0..n]，其中isPrime[i]表示i是否为质数，初始值都设为true。

2. 将数组的第一个元素（即0和1）标记为非质数，因为它们不是质数。

3. 遍历从2到sqrt(n)（取整）。对于每个当前遍历的数字i，如果它是质数（isPrime[i]==true），则将它的所有倍数（除了它本身）标记为非质数。这可以通过从i*i开始，每次加i的方式完成，因为所有的合数都能分解成两个较小数的乘积，其中一个必然是之前的某个已经检查过的质数。

4. 遍历结束后，isPrime[]数组中剩余为true的就是质数。例如，isPrime[2], isPrime[3], ..., isPrime[n]分别对应于2, 3, 5, ...这个范围内的质数。

#include <stdio.h>
#include <math.h>

void sieveOfEratosthenes(int n) {
    int isPrime[n + 1];
    for (int i = 0; i <= n; i++)
        isPrime[i] = 1; // 初始化为质数

    isPrime[0] = isPrime[1] = 0; // 0和1不是质数
    for (int i = 2; i * i <= n; i++) { // 只需检查到√n
        if (isPrime[i]) { // 如果i是质数
            for (int j = i * i; j <= n; j += i) // 标记其倍数为非质数
                isPrime[j] = 0;
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i])
            printf("%d ", i); // 打印出质数
    }
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    sieveOfEratosthenes(n);
    return 0;
}