埃拉托色尼筛法——C语言实现

Question

我遗漏了一些东西，但我找不到它是什么。我也得到了一个 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 function

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

Answer 1

重新格式化代码

帮助您的一个常见步骤是向我们格式化

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

int main ( void )
{
  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;
      }
    }
  }

  for ( int i = 0; i < laenge; i++ )
  {
    printf( "%d, ", array[i] );
  }

  printf( "\n" );
  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" );
}

注意：此风格是个人风格，并不打算像我一样使用间距或卷曲括号进行宗教般的激烈战争。

读取时发现错误：

您使用 C99。在改变某些东西之前考虑到这一点。（懂你的语言）

您分配了 n - 1 个元素的内存，但您尝试从元素 2 访问到元素 n，两者都包括第一个 for 环形。（了解内存分配的工作原理）

数组从零开始（插入笑话），因此，您无法到达元素 n 或元素 n - 1.

print_prim 只打印包含 1 的数组元素的值加 2。换句话说：尝试定位数组中所有包含 1 的位置，然后将该位置递增 2。（知道如何阅读调试）

我建议您学习该语言的工作原理，而不是基于 trial'n'error 的编程。它会为你节省很多时间，你会学到更多。

Answer 2

您只需要一个移动 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 作为包含打印的第二个参数。

埃拉托色尼筛法——C语言实现

Sieve of Eratosthenes - C language implementation

c

for-loop

sieve

sieve-of-eratosthenes

重新格式化代码

读取时发现错误：