풀이
유클리드 호제법은 최대공약수를 구하는 알고리즘이다.
- 두 수 N, M (N > M)을 입력받는다.
- N을 M으로 나누었을 때의 몫과 나머지가 N, M이 되며 이 과정을 나머지가 0이 될 때 까지 반복한다.\
- 나머지가 0이 될때의 N(몫)이 최대공약수이다.
- 두 수 N, M의 곱은 최대공약수(GCD)와 최소공배수(LCM)의 곱과 같다.
소스코드
#include <stdio.h>
int euclidean_gcd(int n, int m){
return m ? euclidean_gcd(m, n%m) : n;
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
int gcd = euclidean_gcd(n, m);
printf("%d\n%d", gcd, n*m / gcd);
}
출처 및 참고자료
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 11650] 좌표 정렬하기 [C] (0) | 2021.07.15 |
---|---|
[백준 2751] 수 정렬하기 2 [C] (0) | 2021.07.15 |
[백준 1181] 단어 정렬 [C] (0) | 2021.07.15 |
[백준 1259] 팰린드롬수 [C] (0) | 2021.07.15 |
[백준 1018] 체스판 다시 칠하기 [C] (0) | 2021.07.15 |