1447. 最简分数

from typing import List


class Solution:
    @staticmethod
    def gcd(denominator, numerator):
        while numerator != 0:  # 辗转相除
            denominator, numerator = numerator, denominator % numerator
        return denominator

    def simplifiedFractions(self, n: int) -> List[str]:
        ret = set()
        for denominator in range(2, n + 1):
            for numerator in range(1, denominator):
                gcd = self.gcd(denominator, numerator)
                ret.add(f'{numerator // gcd}/{denominator // gcd}')

        return list(ret)