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).
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment