What is causing this function to return nothing sometimes?-CodePudding

I have this function that is supposed to return an array of prime numbers from 2 to n, but sometimes it doesn't return anything and just says "exited with code=3221225477", specificaly, if I enter a value over 3 or 4. When it does work, it skips over the number 5 and prints "2 3 29541 7 11 ...".

Can someone point out what's wrong with it?

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int *primes_in_range(int stop){
    int *array_primes = malloc(sizeof(int));
    int size = 1;
    int aim;
    int prime;

    array_primes[0] = 2;

    for (int number = 3; number <= stop; number  = 2){
        aim = sqrt(number);

        for (int index = 0; index < size; index  ){
            prime = array_primes[index];

            if ((number % prime) == 0){
                break;
            }
            else if (prime >= aim){
                array_primes = realloc(array_primes, sizeof(int)*size);
                array_primes[size] = number;
                size  = 1;
                break;
            }
        }
    }
    return array_primes;
}

int main(){
    int *result = primes_in_range(8);
    
    for (int i=0; i<8; i  ) printf("%d\n", result[i]);
    free(result);

    return 0;
}

I wrote a program following the same algorithm in python and it didn't skip any numbers, so it must be for a different reason that it doesn't work unless I missed something.

I'll leave the working python code here:

def primes_in_range(stop: int = None):
    prms = [2]

    for num in range(3, stop 1, 2):
        aim = num**0.5

        for prm in prms:
            if not num % prm:
                break
            elif prm >= aim:
                prms.append(num)
                break

    if stop >= 2:
        return prms
    else:
        return []


print(primes_in_range(13))

CodePudding user response：

You need to increment the size variable before the call to realloc, then use size - 1 as the index for the new value. As it stands, your program is writing to a value (array_primes[size]) that is outside the range of the allocated buffer and will cause undefined behaviour (which will crash the program … sometimes).

Further, the 'weird' numbers you are seeing at the end of your list are also values being read from beyond the allocated buffer, because you always assume there will be 8 values (which there won't be). To fix this, add another int* parameter to your function that can return the number of prime number that it found – and use that as the terminator value for your printf loop:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int* primes_in_range(int stop, int* found) {
    int* array_primes = malloc(sizeof(int));
    int size = 1;
    int aim;
    int prime;

    array_primes[0] = 2;

    for (int number = 3; number <= stop; number  = 2) {
        aim = sqrt(number);

        for (int index = 0; index < size; index  ) {
            prime = array_primes[index];

            if ((number % prime) == 0) {
                break;
            }
            else if (prime >= aim) {
                size  = 1; // Increase size BEFORE reallocating!
                array_primes = realloc(array_primes, sizeof(int) * size);
                array_primes[size - 1] = number; // The last (new) entry is at index "n - 1"
                break;
            }
        }
    }
    *found = size; // So we know how many were found
    return array_primes;
}

int main() {
    int total = 0;
    int* result = primes_in_range(8, &total);

    for (int i = 0; i < total; i  ) printf("%d\n", result[i]); // Stop at found number
    free(result);

    return 0;
}

CodePudding user response：

array_primes = realloc(array_primes, sizeof(int)*size);
array_primes[size] = number;
size  = 1;

This is not how you append an element to an array. A correct version could be:

size  = 1; // first increase the size
array_primes = realloc(array_primes, sizeof(int)*size); // realloc to new size
array_primes[size-1] = number; // access last element, as usual

Also you are returning an array but the caller has no idea what its size is. Either return a structure with the array and its size or pass a size by address to fill in (out parameter) that could also serve as a maximum size.

CodePudding user response：

As @WeatherVane noted, your mallocs/remallocs are wrong. Personally I would take a more direct approach and use a single operation:

 int *array_primes = calloc(stop 1, sizeof(int));

This allocates the worst case size at the very beginning, with a safety margin. Reallocs are horridly inefficient and use of them for small sizes is ugly. All the extra instructions in such code to handle realloc() also take space... so even if a simple malloc() grabs a little extra memory you are usually still ahead in the memory game by dropping the remallocs() and supporting code. It's simpler to debug as well.

The lack of remalloc() allows you to really simplify your loops.

Callers stepping through the results can also break early if a zero is encountered for whatever reason. Across decades of programming I've become very paranoid about things like this.