Решето Эратосфена — реализация на языке C

Все, что вам нужно, это обычное сито, сдвинутое на 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 в качестве второго аргумента для включительной печати.

Переформатирование кода

Обычный шаг, чтобы помочь вам, — отформатировать для нас

#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 печатает только значение плюс 2 элемента массива, содержащего 1. Другими словами: попробуйте найти все позиции в массиве, который содержит 1, и увеличьте эту позицию на 2. (знать, как читать-отладка< /эм>)