用除余法二维数组找素数 c语言

这里提供一个用除余法（也称为埃氏筛法）查找素数的C语言代码，其中使用了一个二维数组来存储筛选结果：

#include <stdio.h>

#define N 100

int main()
{
    int i, j;
    int is_prime[N+1][N+1]; // 二维数组，is_prime[i][j] 表示 i * j 是否为素数

    // 初始化数组
    for (i = 2; i <= N; i++) {
        for (j = 2; j <= N; j++) {
            is_prime[i][j] = 1;
        }
    }

    // 使用除余法筛选素数
    for (i = 2; i <= N; i++) {
        for (j = 2; j <= N; j++) {
            if (is_prime[i][j] && i * j <= N) {
                // i * j 是合数，将 is_prime[i*j] 标记为 0
                is_prime[i*j][1] = 0;
            }
        }
    }

    // 输出素数
    printf("2 ");
    for (i = 3; i <= N; i++) {
        if (is_prime[i][1]) {
            printf("%d ", i);
        }
    }

    return 0;
}

在这个代码中，我们使用一个二维数组 `is_prime` 来存储筛选结果。其中，`is_prime[i][j]` 表示 `i * j` 是否为素数。初始时，我们将所有的 `is_prime[i][j]` 都设置为 1。

接着，我们使用除余法对素数进行筛选。具体地，我们从 2 开始遍历每个数 `i` 和 `j`，如果它们的乘积 `i * j` 是合数，就将 `is_prime[i*j][1]` 标记为 0。最后，我们遍历二维数组 `is_prime`，输出所有标记为 1 的素数。

这个算法的时间复杂度为 $O(N^2 \log \log N)$，其中 $N$ 是最大的素数范围。虽然时间复杂度比较高，但是这个算法的优点是可以在有限的空间内处理较大范围的素数。