2022/02/10
这题主要考察辗转相除法
Java:
class Solution {
public int gcd(int a, int b) {
if (a % b == 0) return b;
return gcd(b, a % b);
}
public List<String> simplifiedFractions(int n) {
List<String> ans = new ArrayList<>();
for (int q = 2; q <= n; q++) {
for (int p = 1; p < q; p++) {
if (gcd(q, p) == 1) {
ans.add(p + "/" + q);
}
}
}
return ans;
}
}
javascript:
function gcd(a, b) {
if (a % b == 0) return b;
return gcd(b, a % b);
}
var simplifiedFractions = function(n) {
let ans = [];
for (let q = 2; q <= n; q++) {
for (let p = 1; p < q; p++) {
if (gcd(q, p) === 1) {
ans.push(`${p}/${q}`);
}
}
}
return ans;
};