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

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

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

 

입력받은 두 자연수의 최대공약수와 최소공배수를 구하는 문제

 

#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 lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

int main() {
	int n1, n2;
	cin >> n1 >> n2;
	cout << gcd(n1, n2) << "\n" << lcm(n1, n2);
}

최대공약수

자연수 a와 b가 주어졌을때 a%b = c를 구하면

b와 c의 최대공약수는 a와 b의 최대 공약수와 같다

-> 이를 계속 반복하여 c가 0일때 b 값이 최대 공약수

 

최소공배수

a*b/(gcd)