最简分数

import java.util.ArrayList;
import java.util.List;

/**
 * @author yagol
 * @date 2022-02-10 上午9:20
 * @desc the description of this class
 **/
class Solution1447 {
    public static void main(String[] args) {
        System.out.println(new Solution1447().simplifiedFractions(
                4
        ));
    }

    public List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (gcd(j, i) == 1) {
                    res.add(j + "/" + i);
                }
            }
        }
        return res;
    }

    /**
     * 最大公约数
     *
     * @param a
     * @param b
     * @return
     */
    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}