c语言用筛选法求素数

在C语言中，我们可以使用筛选法（Sieve of Eratosthenes）来求解一串数字中的素数。这是一种古老的算法，用于找到一定范围内所有整数中的素数。以下是基本步骤：

1. **创建一个布尔数组**：假设我们想要找出从2到n的所有素数，创建一个大小为(n+1)的布尔数组，初始时所有的元素值都设为`true`，因为我们都认为每个数字开始时可能是素数。

2. **初始化第一个素数**：将数组的第一个元素（索引0）设置为`false`，因为1不是素数。

3. **遍历并标记合数**：从2开始，对于每一个小于等于√n的素数，将它的倍数（除了它自身）的数组元素都设为`false`。因为如果一个数能被另一个数整除，那么这个数就不是素数。

4. **检查并记录素数**：在遍历过程中，发现数组中值为`true`的位置即为素数。把对应的索引数值添加到结果列表或数组中。

5. **重复过程直到结束**：每次找到一个素数后，更新范围上限为当前素数的平方根，再继续下一轮筛选。

下面是一个简单的C语言函数示例，实现了上述步骤：

#include <stdio.h>
#include <stdbool.h>
#define LIMIT 100

void sieve_of_eratosthenes(int limit, int primes[]) {
    bool is_prime[LIMIT + 1];
    for (int i = 0; i <= LIMIT; i++)
        is_prime[i] = true;

    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= LIMIT; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i <= LIMIT; i += p)
                is_prime[i] = false;
        }
    }

    int count = 0;
    for (int p = 2; p <= LIMIT; ++p)
        if (is_prime[p])
            primes[count++] = p;
}

int main() {
    int prime_numbers[LIMIT / 2];
    sieve_of_eratosthenes(LIMIT, prime_numbers);
    printf("Prime numbers up to %d are:\n", LIMIT);
    for (int i = 0; i < count; ++i)
        printf("%d ", prime_numbers[i]);
    return 0;
}