Instantly share code, notes, and snippets.

Embed
What would you like to do?
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