[프로그래머스] 최대공약수와 최소공배수

문제

최대공약수와 최소공배수

[유클리드의 호제법]

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int c;
    int a = n;
    int b = m;
    while(b){
        c = a % b;
        a = b;
        b = c;
    }
    answer.push_back(a);
    answer.push_back(n*m/a);
    return answer;
}

---

해설

유클리드의 호제법

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
최대공약수와 최소공배수를 구할 수 있는 알고리즘 이다.

int a , b;
int c;

while(b){
        c = a % b;
        a = b;
        b = c;
}

return a;

1. 입력으로 두 수 a,b(a>b)가 들어온다.
2. a가 0이 아니라면, b를 출력하고 알고리즘을 종료한다.
3. b이 a으로 나누어 떨어지면, a를 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면 b를 a로 나눈 나머지를 새롭게 a에 대입하고, b와 a를 바꾸고 3번으로 돌아온다.

최소공배수 = a * b / 최대공약수이다.