C++:: 프로그래머스 < 최대공약수와 최소공배수 >

제목 그대로 구하면 되는 문제이다.
유클리드 호제법이라는 최대공약수를 구하는 알고리즘도 존재한다.

#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

void getElements(int num, unordered_map<int, int>& um) {// 공약수를 구해준다.
    while (num > 1) {
        for (int i=2; i<=num; i++) {
            if (num%i == 0) {
                um[i]++;
                num /= i;
                break ;
            }
        }
    }
}

vector<int> solution(int n, int m) {
    vector<int> answer(2, 1);
    unordered_map<int, int> um_n, um_m;
    getElements(n, um_n);
    getElements(m, um_m);
    for (auto c : um_n) {
        if (um_m[c.first]) {
            answer[0] *= c.second > um_m[c.first] ? pow(c.first, um_m[c.first]) : pow(c.first, c.second);
        }
        um_m[c.first] = c.second > um_m[c.first] ? c.second : um_m[c.first];
    }
    for (auto c : um_m) {
        answer[1] *= pow(c.first, c.second);
    }
    return answer;
}

유클리드 호제법 풀이

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b) {// 최대 공약수
	return (b ? gcd(b, a%b) : a);
}

int lcm(int a, int b) {// 최소 공배수
	return (a*b / gcd(a, b));
}

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