欧拉筛法求素数c语言代码

好的，欧拉筛法求素数的C语言代码如下：

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

#define MAX_N 1000000

int primes[MAX_N];  // 存储素数
bool is_prime[MAX_N+1];

int sieve(int n)
{
    int p = 0;
    for (int i = 0; i <= n; ++i) {
        is_prime[i] = true;
    }
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes[p++] = i;
            for (int j = i * 2; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return p;
}

int main()
{
    int n = 100;
    int count = sieve(n);
    printf("The number of primes less than or equal to %d is %d.\n", n, count);
    printf("The primes are:\n");
    for (int i = 0; i < count; ++i) {
        printf("%d\n", primes[i]);
    }
    return 0;
}

欧拉筛法的主要思想是：在每次筛数的过程中，用已有的素数来筛掉比它大的素数及其倍数。这样可以避免重复筛数，提高算法效率。

具体实现时，我们可以先用一个bool型数组is_prime来标记每个数是否是素数。从2开始遍历到n，如果当前数是素数，就把它作为新的素数，并把它的倍数标记为非素数。最后把所有素数存入primes数组中。

上述代码中，sieve()函数返回的是数组primes中存储的素数个数。对于n=100的情况，输出的结果如下：

The number of primes less than or equal to 100 is 25.
The primes are:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97