筛选法求素数c 语言

筛选法是一种常见的求解素数的经典算法，比如埃拉托斯特尼筛法（Sieve of Eratosthenes）。在C语言中，可以按照以下步骤编写一个简单的埃拉托斯特尼筛法：

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

#define MAX_PRIME 10000 // 设置最大的素数范围

bool is_prime(int num) {
    if (num <= 1)
        return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

void sieve_of_eratosthenes() {
    bool prime[MAX_PRIME + 1];
    for (int i = 2; i <= MAX_PRIME; i++)
        prime[i] = true;

    for (int p = 2; p * p <= MAX_PRIME; p++) {
        // 如果prime[p]尚未被标记，则p是质数
        if (prime[p]) {
            // 将p的所有倍数标记为非质数
            for (int i = p * p; i <= MAX_PRIME; i += p)
                prime[i] = false;
        }
    }

    printf("Prime numbers are:\n");
    for (int p = 2; p <= MAX_PRIME; p++)
        if (prime[p])
            printf("%d ", p);
}

int main() {
    sieve_of_eratosthenes();
    return 0;
}

这个程序首先创建一个布尔数组`prime[]`表示从2到给定范围内的所有数字是否为素数。然后遍历数组，将每个素数的倍数标记为合数。最后输出所有的未被标记的数，即为素数。