[알고리즘] 최대 공약수, 최소공배수 구하기

문제 - 유클리드 호제법을 이용하여 최대 공약수, 최소공배수 구하기
제한 - 없음

#include <stdio.h>
int main(){
int i = 0;
int j = 0;
int x = 0;

scanf("%d %d", &i, &j);
int k1 = i; // 최소공배수에 쓰일 원래의 수
int k2 = j; // 최소공배수에 쓰일 원래의 수
if(i<j){ // 앞뒤가 바뀌어도 나눌수 있게

int temp;
temp = i;
i = j;
j = temp;
}

do{
x = i%j;
i=j;
j=x;
}while(j != 0);
printf("최대공약수는 %d \n", i);
printf("최소공배수는 %d \n", (k1*k2)/i);
return 0;
}

팁 -

유클리드 호제법
9/6 = 1 나머지 3
6/3 = 2 나머지 0
나머지가 0이 되면 마지막으로 나눴던 3이 최대공약수가 된다.
최소공배수는 두 수의 곱을 최대공약수로 나눈 것이다.
9와 6을 입력하면 그림으로 볼 때

i j x
9 6 3
6 3 0
3 0

x가 0일 때 j 위치에 있는 것이 최대공약수이다.
그러나 while문은 한번 더 돌기 때문에 i를 출력해준다.