Отформатировать дробь в сборщике до наименьшего общего знаменателя?

Современные дети... алгоритм Евклида... чему учат в школе ... ворчать ворчать...

int gcd(int a, int b) {
    // assumes a >= 0 && b > 0
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

NSString *stringByReducingFraction(int a, int b) {
    if (a == 0) return @"0";
    if (a == b) return @"1";

    int g = gcd(a, b);
    return [NSString stringWithFormat:@"%d/%d", a / g, b / g];
}

Это должно работать для любой степени 2 знаменателя:

// dodge this special case:
[fractionArray addObject:@"0"];

for ( int numerator = 1; numerator <= 15; numerator++ )
{
    int denominator = 16;
    int num = numerator;

    while ( num % 2 == 0 )
    {
        num /= 2;
        denominator /= 2;
    }

    NSString *fracString = [NSString stringWithFormat:@"%d/%d", num, denominator];
    [fractionArray addObject:fracString]; // Add the string.
}

И это легко распространить на любой знаменатель. (Подсказка: замените 2 на n, повторите n от 2 до sqrt (знаменатель).)

РЕДАКТИРОВАТЬ: на самом деле работает сейчас!

Поскольку я пошел дальше и закодировал его, вот версия, которая учитывает любой знаменатель:

int denominator = 240;

for ( int numerator = 1; numerator < denominator; numerator++ )
{
    int denom = denominator;
    int num = numerator;
    int factor = 2;

    while ( factor * factor < denom )
    {
        while ( (num % factor) == 0 && (denom % factor) == 0 )
        {
            num /= factor;
            denom /= factor;
        }

        // don't worry about finding the next prime,
        // the loop above will skip composites
        ++factor; 
    }

    NSString *fracString = [NSString stringWithFormat:@"%d/%d", num, denom];
    [fractionArray addObject:fracString];
}