[백준]2609번 최대공약수와 최소공배수 c/c++

문제

https://www.acmicpc.net/problem/2609

나의 해결방법
이 문제를 처음봤을땐 우리가 수학으로 푸는 방식으로 자연수 두개가 같은값으로 나눠떨어지지 않을때까지 증가하는 i값으로 구해볼까? 했었는데

ex)

while(1)
if (n % i == 0 && m % i == 0) {
            n /= i;
            m /= i;
            max = max * i;
        } //최대공약수 구하기

이러한 방식으로 코드를 짜게 되면 나눠주는 값을 제대로 설정할 수 없었다.
그리고 while문을 빠져나가야할 조건을 생각해내지 못하였다.

 

유클리드 호제법으로 풀어야한다!

유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘이다.

ex) 1112, 695의 최대공약수 구하기
1. 큰수를 작은 수로 나눈 나머지를 구한다. (mod연산을 한다)
1112 % 695 = 417
2. 나누었던 수와 나머지로 mod연산을 한다.
695 % 417 = 278
3. 과정을 계속 반복한다.
417 % 278 = 139
` 278 % 139 = 0'
--> 139가 최대공약수가 된다.

코드

#include<iostream>

using namespace std;

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


int main() {
    int p, q;
    cin >> p >> q;
    int g = gcd(p, q);
    cout << g << '\n';
    cout << (p * q) / g << '\n';  //최소공배수는 최대공약수 x 나머지가 0이될때까지 나눈 두 수
}