1) You can't. You can make it a reasonable size (like sqrt(n)) and not worry about the wasted space, or you can use dynamic memory allocation (see below).
2) Not really.. you can return a pointer from a function, true. But the pointer can't point to a local array from within the function (the variable will have gone out of scope), it can only point to dynamically allocated memory. And if it's dynamically allocated, you'd just use the pointer directly rather than copying the data into an array, because you'd already have what you needed!
Okay, so the best approach is probably to have getPrimes() use malloc() to dynamically allocate memory for the array, since only getPrimes() knows how big the array should be. Actually, it doesn't even know how big the array should be, but it could allocate some memory and grow it if necessary. Example:
Code:
int *getPrimes(int *count, int max) {
int size = 10; // this keeps track of how many elements are allocated
int *array = malloc(size * sizeof(*array));
*count = 0; // this keeps track of how many elements are used, so *count <= size at all times
for( /* ... */ ) {
// assume x needs to be added to the array.
if(*count + 1 > size) {
// not enough space.
size *= 2;
array = realloc(array, size * sizeof(*array));
}
array[*count] = x;
*count ++;
}
return array;
}
int count;
int *data = getPrimes(&count, n);
// now, data is an array of count elements.
As you can see, it's a bit complicated. But it's worth trying, to get the hang of it, because dynamic memory allocation is very powerful. I suggest you read up on it a bit. Doubling the size of the array is standard practice to make the amortized insertion cost constant (basically, if you always add like +10 every time, it gets very expensive with large arrays). Also, malloc() and realloc() return NULL if there's no more memory available, so you should handle that... but in this example I've glossed over that detail since it's complex enough as it is.
[edit] BTW, sizeof(*array) is the same as sizeof(array[0]), which in this case would be sizeof(int). It's useful to specify sizeof(*array) however, in case the type of array changes from int* to float* or something in the future. Also, sizeof(*array) and sizeof(array[0]) are compile-time expressions, so your program isn't slowed down at all by doing this. [/edit]