Алгоритм решета Эратосфена на C

Хорошо, эта функция, которую я создал, использует решето алгоритма Эратосфена для вычисления всех простых чисел

Когда функция завершается, простые числа должны указывать на кусок динамически выделяемой памяти, который содержит все простые числа *count будет иметь счет простых чисел.

Вот моя функция getPrimes: 

void getPrimes(int num, int* count, int** array){
    (*count) = (num - 1);
    int sieve[num-1], primenums = 0, index, fillnum, multiple;

    //Fills the array with the numbers up to the user's ending number, num.
    for(index = 0, fillnum = 2; fillnum <= num; index++, fillnum++){
        sieve[index] = fillnum;
    }

    /* Starts crossing out non prime numbers starting with 2 because 1 
       is not a prime. It then deletes all of those multiples and 
       moves on to the next number that isnt crossed out, which is a prime. */
    for (; primenums < sqrt(num); primenums++)  //Walks through the array.
    {
        //Checks if that number is NULL which means it's crossed out
        if (sieve[primenums] != 0) {
            //If it is not crossed out it starts deleting its multiples.
            for (multiple = (sieve[primenums]); 
                 multiple < num; 
                 multiple += sieve[primenums]) {  
                //Crossing multiples out 
                //and decrements count to move to next number
                sieve[multiple + primenums] = 0;
                --(*count);
            }
        }
    }
    int k;
    for(k=0; k < num; k++)
        printf("%d n", sieve[k]);

    printf("%d n", *count);
    array = malloc(sizeof(int) * (num + 1));
    assert(array);
    (*array) = sieve;
}

Итак, вот предполагаемый результат и мой результат. Как видите, что-то не так в моей функции getPrimes, но я не уверен, что именно.

Intended Output:

There are 8 prime numbers less than or equal to 19

2  3  5  7  11  13  17  19  

My Output: 

2 
3 
0 
5 
0 
7 
0 
0 
0 
11 
0 
13 
0 
0 
0 
17 
0 
19 
0 
0
Вот 3 проблемы, на которые люди указали мне до сих пор:
  1. неправильный процесс удаления if (sieve[multiple]) { индекс сетки массива имеет смещение
  2. (*array) = sieve; пропускает только что выделенную память и позволяет *array указать на локальную переменную, которая перестает существовать, когда функция возвращает - вы получите висячий указатель.
  3. if(sieve[i] != NULL) следует использовать 0, а не NULL, у вас нет массива указатели.

Однако я не слишком уверен, как исправить проблему с висячим указателем / памятью, которая была замечена для меня. Кроме того, мне было интересно, есть ли что-нибудь еще в моем коде, что имеет ошибки, поскольку я не слишком уверен, почему мои числа в моем выводе добавляют 0...не беспокойтесь о разном стиле вывода, только о дополнительных числах. Спасибо, если вы можете помочь мне с этим!

2 3
primes dangling-pointer

2 ответа:

void getPrimes(int num, int* count, int** array){
    (*count) = (num - 1);
    int sieve[num-1], primenums = 0, index, fillnum, multiple;

Вы объявляете массив num-1 элементов для чисел от 2 до num. Это нормально.

    //Fills the array with the numbers up to the user's ending number, num.
    for(index = 0, fillnum = 2; fillnum <= num; index++, fillnum++){
        sieve[index] = fillnum;
    }

Вы заполняете каждый слот номером, с которым он связан, также хорошо.

     /* Starts crossing out non prime numbers starting with 2 because 1 is not a prime.
        It then deletes all of those multiples and 
        moves on to the next number that isnt crossed out, which is a prime. */
     for (; primenums < sqrt(num); primenums++) //Walks through the array.
Вы останавливаетесь примерно на квадратном корне, это хорошо. 
        {
            if (sieve[primenums] != 0){ //Checks if that number is NULL which means it's crossed out

                   for (multiple = (sieve[primenums]); multiple < num; multiple += sieve[primenums])
                      //If it is not crossed out it starts deleting its multiples.
                   {  //Crossing multiples out and decrements count to move to next number
                            sieve[multiple + primenums] = 0;

У вас тут проблема. Вы останавливаете цикл только тогда, когда multiple >= num, но вы пишете в индекс multiple + primenums, и это часто после конца массива. Например, с num == 19, и primenums == 1 (которые вычеркивает кратные 3), Последняя запись должна индексировать 18 + 1, но последний допустимый индекс - num - 2 = 17.

Смещение индексации точки 1 было исправлено. Но 

                            --(*count);

Здесь вы безусловно декрементируете *count, в более раннем коде вы только декрементировали его, когда sieve[multiple] еще не был вычеркнут. Это правильный путь. Я предлагаю 

for(multiple = primenums + sieve[primenums]; multiple < num - 1; multiple += sieve[primenums]) {
    if (sieve[multiple]) {
         sieve[multiple] = 0;
         --(*count);
    }
}

Чтобы было немного проще.

                   }
            }
        }
        int k;
        for(k=0; k < num; k++)
            printf("%d \n", sieve[k]);

Вы печатаете содержимое sieve независимо от того, является ли оно 0 или нет, и вы также распечатываете sieve[num - 1], которого не существует. Сделай это 

for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        printf("%d\n", sieve[k]);
    }
}

Печатать только простые числа.

            printf("%d \n", *count);
        array = malloc(sizeof(int) * (num + 1));
         assert(array);
         (*array) = sieve;
}

Заменить (*array) = sieve на 

int i = 0;
for(k = 0; k < num-1; ++k) {
    if (sieve[k]) {
        (*array)[i] = sieve[k];
        ++i;
    }
}

Записать только простые числа в *array. Кроме того, вам не нужно выделять (num + 1)*sizeof(int), а только *count * sizeof(int) для этого.

3

Числа, которые вы печатаете, имеют решето, поэтому все числа, которые не являются простыми, имеют значение 0. Попробуйте напечатать следующим образом

for (k = 0; k < num; k++)
if (sieve[k] != 0)
{
        printf(" %d\n", sieve[k]);
}
printf("\n");

Также не следует возвращать локальный массив sieve через параметр array, так как он находится в стеке и больше не будет доступен при возврате функции.

2