c - Eratosthenes筛-C语言实现

我错过了一些东西，但找不到。我还得到了一个input2.c文件，它具有一个print_prim函数，不允许我对其进行更改。

对于n = 10，它始终在打印

4, 5, 7, 9,

我知道 print_prim 函数中有一个i + 2，但我无法解决。同样，我不允许更改print_prim函数。谁能看到我想念的东西吗？


main.c

#include <stdio.h>
#include <stdlib.h>
#include "input2.h"

int main() {
    int n = lese_int();
    int laenge = n-1;
    int *array;
    array = malloc(sizeof(int) * laenge);
    for (int i = 2; i <= n; i++) {
        array[i] = 1;
    }

    for(int i=0;i<=n;i++) {
        if(array[i] == 1){
            for(int j = i ; i*j <= n ; j++){
                array[i*j] = 0;
            }
        }
    }
    print_prim(array, laenge);
    free(array);
    return 0;
}

print_prim函数

void print_prim(int *array, int laenge) {
    for (int i=0; i<laenge; i++) {
        if (array[i] == 1) {
            printf("%d, ", i+2);
        }
    }
    printf("\n");
}

最佳答案

您只需要移动2个元素的普通筛网即可。

int main() {
  int n;
  scanf("%d", &n);

  int *a = (int*)malloc(sizeof(int) * (n - 1));
  for (int i = 0; i < n - 1; i++ ) a[i] = 1;

  for (int i = 2; i*i <= n; i++) {
    if (a[i-2] == 1) {
      for (int j = i * i; j <= n; j+=i ) a[j-2] = 0;
    }
  }

  print_prim(a, n - 1);

  free(a);
  return 0;
}

说明:

分配n-1元素以表示从2到n(含)的数字。

用1初始化所有元素。为什么？因为查看print_prim，它会打印等于1的值。因此，我们所有的素数都需要移动2，并且它的值应该是1。

从2开始，我们将所有质数倍数标记为0。保留1的是素数。有关详细信息，请参见https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。

由于print_prim被2移位了，我们需要将n-1传递为包含打印的第二个参数。