Return to Answer

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.

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.

NSMutableArray * primeFactorization(long n) {
 
 NSMutableArray *factors = [NSMutableArray array];
 
 // Divide by 2:
 while (n > 1 && n % 2 == 0) {
 [factors addObject:@(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;
 }
 
 // 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;
}

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;
 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;
}

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;
}

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;
}

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.