Сито Эратосфена - реализация языка Си - PullRequest
Новая
       57

Сито Эратосфена - реализация языка Си

0 голосов
/ 24 октября 2018

Я что-то упускаю, но не могу найти, что это.Мне также дали файл input2.c, и у него есть функция print_prim, которую я не могу изменять.

Для n = 10 всегда печатается 

4, 5, 7, 9,

Я знаю тамэто функция i + 2 в print_prim , но я не могу ее решить.Опять же, мне не разрешено изменять функцию 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");
}

Ответы [ 2 ]

0 голосов
/ 24 октября 2018

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

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

Обычный шаг, который поможет вам - это отформатировать нам 

#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 цикл.( знает, как работает выделение памяти )

Массивы начинаются с нуля ( insert joke ), поэтому вы не можете добраться до элемента n ни элемент n - 1.

print_prim печатает только значение плюс 2 элемента массива, который содержит 1. Другими словами: попробуйте найти все позиции в массиве, который содержит 1, иувеличьте эту позицию на 2. ( умеете читать и отлаживать )

Я рекомендую вам изучить, как работает язык вместо trial'n'error на основе программирования.Это сэкономит вам много часов, и вы узнаете больше.

...