CODEWITHSUNDEEP
mathlogicfractions
frontendbeast
frontendbeast

Reputation: 1043

Return list of simplest fractions for a given number

I'm trying to create a function that will generate a list of all the simplest fractions for a given number. I'm not fussed about what language an example is given in, it's more the logic I'm trying to get my head around.

I'm not sure if I'm heading in the right direction by iterating through every possible fraction or if there's a better way, or how to find the simplest expression of the fraction.

Pseudo code: 

denominator = 12;
for (i = 1; i <= denominator; i++) {
    for (n = 1; n <= denominator; n++) {
        // find simplest expression of fraction when n!=i
    }
}

Any help would be greatly appreciated, thanks!

Upvotes: 0

Views: 147

Answers (1)

D Stanley
D Stanley

Reputation: 152624

You don't need the inner for-loop, just a method to find the Greatest Common Divisor in order to reduce the fraction:

int denominator = 12;
for (int i = 1; i < denominator; i++) {  // note change from <= to <
    int gcd = GCD(i, denominator);
    // answer will be "{i/gcd}/{denominator/gcd}"
}

Upvotes: 2

Related Questions