PS/Baekjoon Online Judge

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

kimyoungrok 2021. 7. 15. 11:15

백준 - 2609


풀이

유클리드 호제법은 최대공약수를 구하는 알고리즘이다.

  1. 두 수 N, M (N > M)을 입력받는다.
  2. N을 M으로 나누었을 때의 몫과 나머지가 N, M이 되며 이 과정을 나머지가 0이 될 때 까지 반복한다.\
  3. 나머지가 0이 될때의 N(몫)이 최대공약수이다.
  4. 두 수 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);
}

출처 및 참고자료

 

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

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

www.acmicpc.net

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를

ko.wikipedia.org