One question per day 1447 Simplest fraction

topic ： Give you an integer n , Please return to all 0 To 1 Between （ barring 0 and 1） Satisfy that the denominator is less than or equal to n Of Simplest fraction . The score can be in the form of arbitrarily Sequential return .

Explain : Find the simplest fraction , The greatest common divisor equivalent to denominator and numerator is 1.

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        for i in range(2,n+1):
            for j in range(1,i):
                if gcd(i,j) == 1:
                    ff = f"{j}/{i}"
                    res.append(ff)
        return res

  greatest common divisor gcd(a,b) yes Python Built in functions , You can use it directly .

gcd Recursive implementation of

def gcd(a,b):
    return a if b == 0 else gcd(b, a%b)