#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define MAX_DIVISORS 100

int getDivisors(int *factors, int n) {
    int count = 0;
    for (int i = 1; i <= n / 2; i++) {
        if (n % i == 0) {
            factors[count++] = i;
        }
    }
    factors[count++] = n;
    return count;
}

int main() {
    int k = 10;
    int denom = 32767;
    int base = 48000;

    int divisors[MAX_DIVISORS];
    int divCount = getDivisors(divisors, base);
    double goal = (double)k / denom;

    int bestF = 0;
    int bestI = 1;
    double best = 1;

    clock_t start = clock();

    for (int i = 1; i <= base; i++) {
        for (int f = 0; f < divCount; f++) {
            if (i > divisors[f])
                continue;

            double res = fabs(goal - (double)i / divisors[f]);

            if (res < best) {
                best = res;
                bestI = i;
                bestF = f;
            }
        }
    }

    clock_t end = clock();
    double elapsed = (double)(end - start) * 1000.0 / CLOCKS_PER_SEC;

    printf("%d/%d\n", k, denom);
    printf("Found best approx: %d/%d (%f, err = %.3g) in %.3f ms\n", bestI, divisors[bestF], (double)bestI / divisors[bestF], best, elapsed);

    return 0;
}