[백준 2609] 최대공약수와 최소공배수

문제

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이될때까지 나눈 두 수
}