1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// @Title: 最简分数 (Simplified Fractions)
// @Author: 15816537946@163.com
// @Date: 2022-02-10 10:42:15
// @Runtime: 44 ms
// @Memory: 6.9 MB
func simplifiedFractions(n int) (ans []string) {
    for denominator := 2; denominator <= n; denominator++ {
        for numerator := 1; numerator < denominator; numerator++ {
            if gcd(numerator, denominator) == 1 {
                ans = append(ans, strconv.Itoa(numerator)+"/"+strconv.Itoa(denominator))
            }
        }
    }
    return
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}