최대공약수와 최소공배수 풀이

문제 링크: https://www.acmicpc.net/problem/2609

백준 정수론 및 조합론 3단계 - 2609번 최대공약수와 최소공배수를 풀어보았다.

 

풀이: 유클리드 호제법을 이용해 최대공약수를 구하고, 두 수의 곱을 최대공약수로 나누는 것으로 최소공배수를 구할 수 있다.

C++은 numeric 헤더에 있는 gcd와 lcm을 이용했다.

 

C++

#include <iostream>
#include <numeric>

using namespace std;

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

Python

def gcd(a,b):
	if b==0: return a
	else: return gcd(b,a%b)

a,b=map(int,input().split())
x=gcd(a,b)
print(x)
print(int(a*b/x)) # int를 안하면 실수 형태로 출력된다

Java