Simplified Fractions

1447. Simplified Fractions

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> result;
        for (int b = 2; b <= n; ++b) {
            for (int t = 1; t < b; ++t) {
                if (__gcd(t, b) == 1) {
                    result.push_back(to_string(t) + "/" + to_string(b));
                }
            }
        }
        return result;
    }
};

만들어질 수 있는 분수 중 기약분수만 적어야 하므로 최대공약수가 1인 값만 결과에 넣어준다.

Time: O((n^2)log(n))

• 분모 순회 n * 분자 순회 n * 최대공약수 log(n)

Space: O(1)

• 답 array 제외하고 필요한 공간 1