Find optimal factors for number, with a specified largest acceptable factor. Used to find best possible (realistic, in my case 1:7) gear ratio for spinning a telescope in sidereal time (~86164 seconds).

optimalfactors.c

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

#define FACTOR_LIMIT 100 // Supports atm max 100 factors.

void die(const char *message)
{
	if (errno) {
		perror(message);
	} else {
		printf("%s\n", message);
	}

	exit(1);
}

int smallestFactor(int n)
{
	if (n == 1) {
		return 1;
	}

	int sf = 2; // start from 2 since no 1:1 gears needed.
	for (; sf < n; ++sf) {
		if (n % sf == 0) {
			return sf;
		}
	}

	return sf;
}

// Return array of factors
int *factor(int n, int *factors, int fi)
{
	int sf = smallestFactor(n);

	// Don't include 1 into list of factors because no 1:1 gear ratio needed.
	if (sf == 1) {
		return factors;
	}

	factors[fi] = sf;

	return factor((n / sf), factors, ++fi);
}

int isAcceptableFactors(int *factors, int maxFactor) {
	int isAcceptable = 1;

	// If any of factors is larger than max, deem them unacceptable.
	for (int i = 0; i < FACTOR_LIMIT; ++i) {
		if (factors[i] > maxFactor) {
			isAcceptable = 0;
		}
	}

	return isAcceptable;
}

int *getOptimalFactors(int startNum, int maxFactor)
{
	int *optimalFactors = malloc(FACTOR_LIMIT * sizeof(int));

	if (!optimalFactors) {
		die("Memory error.");
	}

	int optimalsFound = 0;
	int diff = 0;

	while (!optimalsFound && diff < startNum) {
		// Look for optimal factors in both increasing and decreasing ways of start num.
		int *decFactors = malloc(FACTOR_LIMIT * sizeof(int));
		int *incFactors = malloc(FACTOR_LIMIT * sizeof(int));

		if (!decFactors || !incFactors) {
			die("Memory error.");
		}

		decFactors = factor(startNum - diff, decFactors, 0);
		incFactors = factor(startNum + diff, incFactors, 0);

		if (isAcceptableFactors(decFactors, maxFactor)) {
			optimalFactors = decFactors;
			optimalsFound = 1;
		}

		if (isAcceptableFactors(incFactors, maxFactor)) {
			optimalFactors = incFactors;
			optimalsFound = 1;
		}

		diff += 1;
	}

	return optimalFactors;
}

int main(int argc, char *argv[])
{
	if (argc != 3) {
		die("Usage: ./optimalfactors [startNum] [maxFactor]\nExample: ./optimalfactors 86164 7");
	}

	int startNum = atoi(argv[1]);
	int maxFactor = atoi(argv[2]);
	int *factors = getOptimalFactors(startNum, maxFactor);
	int optimalNum = factors[0];

	for (int i = 0; i < FACTOR_LIMIT; i++) {
		if (factors[i] > 0) {
			printf("%d", factors[i]);

			if (factors[i+1] > 0) {
				printf(", ");
				optimalNum *= factors[i+1];
			}
		}
	}
	printf("\n%d (diff: %d)\n", optimalNum, optimalNum - startNum);

	return 0;
}