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

#include <iostream>
using namespace std;

int main(int argc, char **argv){
    int a, b, maxNum = 1, minNum = 0, div = 1;
    scanf("%d %d",&a,&b);

    for(int i=2; i <= min(a, b); i++){
        if(a % i == 0 && b % i == 0){
           maxNum = i;
        }
    }
    printf("%d\n", maxNum);
        

    while(minNum == 0){
        if((b * div) % a == 0){
            minNum = b * div;
            printf("%d", minNum);
        }
        div++;
    }

    return 0;
}

오늘의 키포인트

• 최소 공배수 초기화는 1로
• 유클리드 호제법 사용하기 (위의 코드에서는 사용하지 않았음)

유클리드 호제법

두 수의 최대공약수(GCD)를 구하는 알고리즘

• MOD 연산 : 두 값을 나눈 나머지를 구하는 연산

1. 큰 수를 작은 수로 나눈 나머지를 구한다. -> MOD 연산
2. 나눴던 수와 나머지로 또 MOD 연산을 한다. (반복)
3. 나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 수가 최대공약수.

   그냥 MOD 연산을 반복 수행하면 된다.

반복문

int GCD(int a, int b){
  int tmp;
  while(b){      //b가 0이 될 때까지
    tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}

재귀함수

int GCD(int a, int b){
  return b ? GCD(b, a % b) : a;
}

최소공배수(lcm(a,b)) = a * b / gcd(a,b)

int gcd(int a, int b);

int lcm(int a, int b){
	return (a * b) / gcd(a, b);
}