c语言复现埃拉托色尼筛选法

埃拉托色尼筛法（Sieve of Eratosthenes）是一种古老的算法，用于找出所有小于给定数n的质数。在C语言中复现这个算法，你可以按照以下步骤编写：

1. 定义一个数组`isPrime`，大小为n+1，初始化所有元素为true。这是为了表示每个数默认认为可能是质数。

2. 遍历从2开始的所有数，直到sqrt(n)（n的平方根）。这是因为大于n的因子肯定有一个已经小于等于sqrt(n)。

3. 对于每个遍历到的数i，如果`isPrime[i]`为true，说明它是质数，将它的所有倍数标记为非质数。这可以通过遍历`i*i`到n的范围，并对`isPrime`数组进行更新，将对应位置的值设为false。

4. 当遍历结束后，未被标记为非质数的数组索引就是质数。

以下是简单的C语言代码实现：

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

void sieveOfEratosthenes(int n) {
    bool isPrime[n + 1];
    for (int i = 0; i <= n; i++)
        isPrime[i] = true;

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    printf("质数序列：");
    for (int p = 2; p <= n; p++)
        if (isPrime[p])
            printf("%d ", p);
}

int main() {
    int n = 100; // 想要查找小于这个数的质数
    sieveOfEratosthenes(n);
    return 0;
}