Programers:最大公倍数/最小公倍数(ユークリッドアーク)


ユークリッドアークほう



*aとbの최대공약수(gcd)/최대공배수(lcm)成立gcd*lcm=a*b
  • ユークリッド湖製法で、簡単に最大公約数を得ることができる.
  • コード#コード#

    #include <string>
    #include <vector>
    
    using namespace std;
    
    vector<int> solution(int n, int m) {
        vector<int> answer;
        /* 유클리드 호제법 */
        int c,a=n,b=m;
        while(b != 0)
        {
            c = a % b;
            a = b;
            b = c;
        }
        answer.push_back(a);
        // 나오는 a값이 최대공약수이다 (유클리드 호제법)
        answer.push_back(n*m/a);
        return answer;
    }