최소공배수(lcm), 최대공약수(gcd)

최대공약수는 '유클리드 호제법'을 사용하여 구함!

1. x, y 중 큰수에서 작은수를 나누어 나머지를 구함

2. 1번에서 작은수가 이제 '큰 수' 가 되고 1번에서의 나머지가 작은수

3. 나머지가 0 이 될 때 까지 2번 과정 반복

4. 0이 됬을 때 마지막으로 나눈 값이 최대공약수

최소공배수는 1번에서 처음 x와 y를 곱한 값을 최대공약수로 나누면 된다!

코드

#include <iostream>

#include <stdlib.h>

using namespace std;

int gcd(int a, int b)

{

int n = 0;

while (1)

{

n = a % b;

if (n == 0) return b;

a = b;

b = n;

}

}

int main()

{

int a = 0, b = 0;

cin >> a >> b;

printf("최대공약수는 %d\n", gcd(a, b));

printf("최소공배수는 %d\n", (a*b) / gcd(a, b));

return 0;

}