2609_최대공약수와 최소공배수(유클리드 알고리즘)

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

2609번: 최대공약수와 최소공배수

 

---

 

* 최대공약수 : 공약수 중에서 가장 큰 공약수

 -> 두 수 a, b의 최대공약수는 gcd(a, b) 또는 (a, b)로 나타냄

 

★ 유클리드 알고리즘

 - 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘

 - GCD : Greatest Common Divisor

 - 원리 

  두 수 a(큰 수), b(작은 수)가 있을 때 'a%b=n'계산

   -> n=0 경우 : b가 최대공약수

   -> n≠0 경우 :  a에 b값을 다시 넣고 n을 b에 대입하여 다시 계산

int gcd(int a, int b) {
	int tmp, n;

	//a에 큰 값 배치를 위한 반복문
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	//유클리드 알고리즘 부분
	//a%b진행(b가 0이 될때까지)
	while (b != 0) {
		n = a % b;
		a = b;
		b = n;
	}
	return a;
}

 

---

 

* 최소공배수 : 공배수 중에서 가장 작은 공배수

 -> 두 수 a, b의 최소공배수는 lcm(a, b) 또는 [a, b]로 나타냄

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

 

---

전체 코드

#include <iostream>
#include <cmath>
using namespace std;

int gcd(int a, int b) {
	int tmp, n;

	//a에 큰 값 배치를 위한 반복문
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	//유클리드 알고리즘 부분
	//a%b진행(b가 0이 될때까지)
	while (b != 0) {
		n = a % b;
		a = b;
		b = n;
	}
	return a;
}

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


int main()
{
	int x, y, r1, r2;
	cin >> x >> y;
	r1 = gcd(x, y);
	r2 = lcm(x, y);
	cout << r1 << endl << r2;
}