(프로그래머스 c++)최대 공약수와 최소 공배수

 

int형 변수 n과 m의 최대 공약수와 최소 공배수를 각각 answer에 넣어주면 된다..!

최대 공약수를 구하는 gcd() 함수와 최소 공배수를 구하는 lcm() 함수를 정의하여 사용한다.

 

이때, lcm() 함수에서는 gcd() 함수를 사용한다..!

N과 M의 최대 공약수를 G, 최소 공배수를 L이라 하고,

N과 M을 G로 나누었을 때의 몫을 각각 n, m으로 하자.

 

G )N  M

    a   b

이랬을 때, 최소 공배수 L은

L = G * n * m,

N * M = L * G 의 관계가 나오게 된다.

(L = N * M / G)

그러므로 lcm() 함수는 a * b / gcd(a, b)의 결괏값을 리턴한다...!

 

answer에 각각의 함수의 결과값을 넣어주면 끄으으읏..!

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b)
{
    int c;
    while(b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    answer.push_back(gcd(n, m));
    answer.push_back(lcm(n, m));
    
    return answer;
}