-1
\$\begingroup\$

I made the following code in C, which is supposed to create a list of booleans $n + 1$ long, such that the $i$'th element is true if $i$ is prime and $i$'th element is false if $i$ is not prime (starting the count from zero). So for n = 10, it is supposed to give [false, false, true, true, false, true, false, true, false, false, false].

The logic of the program works, in the sense that the array primes in sieve(long n) is correct. However, when calling it in main, it gives a wrong result. I expect this has something to do with the pointers.

I have another question if that's ok: is it useful to use pointers here? I've been told that pointers are good when working with large amounts of data, but I don't see how it helps as you have to create a normal variable first, the address of which you then assign to the pointer.


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

bool *sieve(long n) {

    bool primes[n + 1]; // we go 0, ..., n such that primes[i] is true iff i is prime

    primes[0] = false;
    primes[1] = false;

    for (int i = 2; i < n + 1; i++) {
        primes[i] = true;
    }

    for (int prime = 2; prime < sqrt(n) + 1; prime++) {
        if (primes[prime]) {
            for (int j = prime*prime; j < n + 1; j += prime) {
                primes[j] = false;
            }
        }
    }

    bool (*primesLocation)[n + 1] = malloc((n + 1) * sizeof(bool));

    primesLocation = &primes;

    return primesLocation;
}


int main(int argc, char **argv){

    bool* primes = sieve(100);

    for (int i = 0; i < 101; i++) {
        if (primes[i]) {
            printf("%d, ", i);
        }
    }
    return 0;
}
\$\endgroup\$
3
  • 3
    \$\begingroup\$ The array primes[] no longer exists when you return from the function. Therefore, the pointer you return is invalid. Create the array in main() and give sieve() a pointer to it. \$\endgroup\$
    – G. Sliepen
    Commented Sep 26, 2020 at 14:47
  • 3
    \$\begingroup\$ Welcome to Code Review, where we review code that is working as expected and provide suggestions on how to improve that code. Can you explain exactly how the result is wrong if the primes are correct? This statement However, when calling it in main, it gives a wrong result. I expect this has something to do with the pointers. makes the question off-topic because the code isn't working as expected. \$\endgroup\$
    – pacmaninbw
    Commented Sep 26, 2020 at 14:50
  • \$\begingroup\$ @G.Sliepen VTC, the code is definitely broken. \$\endgroup\$
    – pacmaninbw
    Commented Sep 26, 2020 at 15:15

1 Answer 1

2
\$\begingroup\$

Your function is mallocing a value, and then overwriting it with a pointer to a local array, and then return the pointer to local array, which doesn't exist after the end of the function.

This may work in certain cases, not work in others, and crash in others.

This line doesn't copy the array, it changes the pointer. You probably meant for this line:

primesLocation = &primes;

to be this:

memcpy(primesLocation, primes, (n + 1) * sizeof(bool));

However you don't need the memcopy - just use the one array:

    bool* primes = malloc(sizeof(bool) * n + 1);
    
    primes[0] = false;
    primes[1] = false;

    for (int i = 2; i < n + 1; i++) {
        primes[i] = true;
    }

    for (int prime = 2; prime < sqrt(n) + 1; prime++) {
        if (primes[prime]) {
            for (int j = prime*prime; j < n + 1; j += prime) {
                primes[j] = false;
            }
        }
    }

    return primes;

This works. However it has the nasty side effect that the caller needs to remember to free the memory otherwise you'll have a leak.

So that the caller doesn't need to free memory that it didn't allocate, consider moving the malloc out of the function and changing this to:

    bool* sieve(long n, bool* primes);

    void main()
    {
      bool* primes = (bool*)malloc(sizeof(bool) * 101);
      auto p = sieve(100, primes);
      free(primes);
    }
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to Code Review! Please note, questions involving code that's not working as intended, are off-topic on this site. If OP edits their post to address the problem and make their post on-topic, they make your answer moot. It is advised not to answer such questions. Protip: There are tons of on-topic questions to answer; you'll make more reputation faster if you review code in questions that will get higher view counts for being on-topic. \$\endgroup\$ Commented Sep 26, 2020 at 16:41
  • \$\begingroup\$ Rather than (n + 1) * sizeof(bool), sizeof primes is simpler, cleaner. \$\endgroup\$ Commented Sep 28, 2020 at 19:57
  • \$\begingroup\$ What is auto p trying to accomplish here in this C code? Are you thinking of another language? Where is the C auto keyword used? \$\endgroup\$ Commented Sep 28, 2020 at 19:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.