Given that this answer is marked with the c tag, and the user quite appropriately points out that the code is 99% c, I decided that it might be worthwhile to demonstrate how simple the C solution to this problem is.
There are only two aspects of Objective-C the user uses.
NSMutableArray. This is convenient and it handles the resizing of the array for us. However, it's important to note that there's nothing magical about how an NSMutableArray resizes. Objective-C mutable arrays are resized in the same way as a C-array.NSNumber. We don't actually see NSNumber anywhere directly, but that's what the @() syntax is doing--creating NSNumber objects. And why? Because NSArray can not store primitive data types. It must store pointers.
Unless the actual intent is to use this array in some other Objective-C code where the NSNumber objects will actually be easier to deal with, there's not a particularly good reason to use Objective-C here, except perhaps being uncomfortable in working with C-style arrays.
So, here's my solution to this problem in C.
As a starting point, I used Martin R's answer, which actually also is very similar to the algorithm I used for a slightly different problem here.
Please note, the following code snippet includes the code from Martin's answer so that the two solutions can be compared side-by-side in case he ever edits/removes his answer.
Martin's very good answer:
NSMutableArray * primeFactorization(long n) {
NSMutableArray *factors = [NSMutableArray array];
// Divide by 2:
while (n > 1 && n % 2 == 0) {
[factors addObject:@(2)];
n /= 2;
}
// Divide by 3, 5, 7, ...
//
// i is a possible *smallest* factor of the (remaining) number n.
// If i * i > n then n is either 1 or a prime number.
for (long i = 3; i * i <= n; i += 2) {
while (n > 1 && n % i == 0) {
[factors addObject:@(i)];
n /= i;
}
}
if (n > 1) {
// Append last prime factor:
[factors addObject:@(n)];
}
return factors;
}
My approach in straight C:
long * cPrimeFactorization(long n, long *factorCount) {
long currentSize = 2;
long currentIndex = 0;
long *factors = malloc(sizeof(long) * currentSize);
while (n > 1 && n % 2 == 0) {
factors[currentIndex++] = 2;
if (currentIndex >= currentSize) {
currentSize *= 2;
long *reallocFactors = realloc(factors, currentSize * sizeof(long));
if (reallocFactors) {
factors = reallocFactors;
} else {
printf("realloc failed");
free(factors);
return NULL;
}
}
n /= 2;
}
for (long i = 3; i * i <= n; i += 2) {
while (n > 1 && n % i == 0) {
factors[currentIndex++] = i;
if (currentIndex >= currentSize) {
currentSize *= 2;
long *reallocFactors = realloc(factors, currentSize * sizeof(long));
if (reallocFactors) {
factors = reallocFactors;
} else {
printf("realloc failed");
free(factors);
return NULL;
}
}
n /= i;
}
}
if (n > 1) {
factors[currentIndex++] = n;
}
*factorCount = currentIndex;
return factors;
}
Running them side by side:
int main(int argc, const char * argv[]) {
long n = 1234567890;
NSDate *startTime = [NSDate date];
NSArray *oFactors = primeFactorization(n);
NSLog(@"time (Objective-C): %f", -[startTime timeIntervalSinceNow]);
startTime = [NSDate date];
long factorCount;
long * cFactors = cPrimeFactorization(n, &factorCount);
NSLog(@"time (C): %f", -[startTime timeIntervalSinceNow]);
NSLog(@"%@", oFactors);
for (long i = 0; i < factorCount; ++i) {
printf("%li\n", cFactors[i]);
}
return 0;
}
For the sake of benchmarking consistency, I just used the Objective-C approach (because Martin already had it and I didn't feel like looking up a C approach). I tried a handful of different numbers and ran them all multiple times. The C approach runs faster in every case.
More than speed, the C approach actually takes less total memory than the Objective-C approach. Not only does the Objective-C array have more overhead than the C array, (each index is the same size, 8-bytes), but the Objective-C array is an index of pointers to objects. So the Objective-C array is already slightly bigger than the C array, plus there's several magnitudes more memory space for holding all of the NSNumber objects out on the heap as well.
And that we have to spend so much time creating these NSNumber objects out on the stack is part of the reason the Objective-C solution is slower. It's also slower because passing messages to objects (the addObject: we call several times) is very slow compared to being able to directly insert a value in at a memory location (which is what we do with the C-array).
Please note, I'm definitely an Objective-C programmer, and I am not a C programmer in the slightest. My C code almost certainly has room for improvement I'd imagine... but as Objective-C programmers, we must always keep in mind that pure-C should always be an option.
As a note, this speed (and memory) difference becomes particularly noticeable with very large powers of two. For example, with 2^49th, which is 562,949,953,421,312, the Objective-C solution takes almost 3 times as long on my computer.
