[BOJ] 2609. 최대공약수와 최소공배수 (C,Python3)

• 코딩 초보. 구현을 목표로 하였기에 비효율적일 수 있습니다.

---

2609. 최대공약수와 최소공배수 

 

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

 

---

1.Python

 

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

a,b=map(int,input().split())
c=gcd(a,b)
print("%d\n%d" %(c,a*b//c))

유클리드 호제법을 이용하는 문제다. 

 

최대공약수와 최소공배수의 경우, 작은 두 수는 구하기 쉽겠지만 수가 커질 수록 소인수분해를 하기 어려워진다. 이때 이용하는 것이 바로 유클리드 호제법이다! 

 

유클리드 호제법에서 최대공약수를 구하는 방법은 다음과 같다. 

 

만약 m과 n의 최대공약수를 구한다고 해보자. 

 

m을 n으로 나누어 그 나머지를 구한다. 

그 나머지가 0이 아닌 어떤 수가 나왔다면, 그 나머지를 다시 n으로 나눈 나머지를 구한다.

.

.

그 나머지가 0이 될때까지 반복한다. 

이때 나머지가 0이 된다면, 마지막 계산에서 나누는데 사용된 수가 m과 n의 최대공약수가 되는 것이다. 

 

그렇다면 최소공배수는 어떻게 구하는거지? 

쉽다. 중학교때 최소공배수를 어떻게 구했었는지 생각해보자. 

m*n= 최대공약수 * 최소공배수 였음을 금방 떠올릴 수 있을 것이다!

 

따라서, 최소공배수는 m*n에서 유클리드 호제법을 이용해 구한 최대공약수로 나눈 몫이라고 할 수 있다. 

 

먼저 최대공약수를 구하기 위해 반복적으로 나머지가 0이될때까지 작업을 수행한다는 점에서 재귀함수를 활용하였다. 나머지가 0이 아닐때에는, 함수를 다시 호출하여 나누어주었던 수와 그 나머지로 작업을 수행하도록 한다. 

그리고 print문을 이용해 각각 최대공약수과 최소공배수를 출력하도록 했다. 

---

2.C99

 

#include <stdio.h>

int gcd(int a,int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b); 
	}
}
main() {
	int m, n,c;
	scanf("%d %d", &m, &n);
	c = gcd(m, n);
	printf("%d\n%d", c, m * n / c); 
}

변수명을 조금 다르게 했을 뿐이지 구현방법은 파이썬과 똑같았다.