Greatest Common Divisor: recursion from 300 BC

Look at this problem: https://leetcode.com/problems/simplified-fractions/

Given the small N (100), the brute-force solution works just fine: go thru all the possible divisors and numerators (100x100 = 10000), and for each one check whether the Greatest Common Divisor between them is 1. If so, add to the return val. GCD can be calculated in LogN. Hence total execution time becomes N*N*LogN, or around 140,000, which runs very fast. Code is down below.

The Greatest Common Divisor algorithm was proposed by Euclid, back few years ago, in 300 BC. It is a clever and the best algorithm ever devised to determine the GCD of two numbers, running in LogN. You can find it here: https://en.wikipedia.org/wiki/Euclidean_algorithm. 

Cheers, ACC.

 

public class Solution

{

    public IList<string> SimplifiedFractions(int n)

    {

        List<string> retVal = new List<string>();

        for (int d = 1; d <= n; d++)

        {

            for (int nu = 1; nu < d; nu++)

            {

                if (GCD(nu, d) == 1)

                {

                    retVal.Add(nu.ToString() + "/" + d.ToString());

                }

            }

        }

        return retVal;

    }

    private int GCD(int a, int b)

    {

        while (a != 0 && b != 0)

        {

            if (a > b)

                a %= b;

            else

                b %= a;

        }

        return a == 0 ? b : a;

    }

}