[SCCC] 최대공약수와 최소공배수_2609번

최대공약수와 최소공배수_2609번

코드

#include <bits/stdc++.h>
using namespace std;

//최대공약수 -> 유클리드 호제법
int GCD(int a, int b) {
    return b ? GCD(b, (a%b)) : a;
}

//최소공배수 -> a*b == GCD(a,b) * LCM(a,b) 
int LCM(int a, int b) {
  return a * b / GCD(a, b);
}


int main() {
    int n, m;
    cin >> n >> m;
    
    cout << GCD(n,m) << "\n" << LCM(n,m);
    
    return 0;
}

---

풀이노트

최대공약수 : 약수 중 가장 큰 값
최소공배수 : 배수 중 가장 작은 값

[최대공약수 - GCD]

• 정석 : 소인수 분해 후, 공통값 중에 가장 큰 값
• 유클리드 호제법 : 효율적으로 최대공약수(GCD)를 구할 수 있음
  • MOD 연산 : 두 값을 나눈 나머지를 구하는 연산
    예 : 1112, 417

1. 큰 수를 작은 수로 나눈 나머지를 구한다
   1112 mod 695 = 417

2. 나눴던 수와 나머지를 MOD 연산한다
   695 mod 417 = 278

3. 반복
   417 mod 278 = 139
278 mod 139 = 0

4. 나머지가 0이 됐을 때,
   마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수가 됨

• 정리
  • 유클리드 호제법은 나눗셈(MOD 연산) 만 반복해서 최대공약수(GCD) 를 구할 수 있음
  • 두 개의 수가 아무리 커도 정해진 순서로 계산하면 효율적으로 최대공약수를 구할 수 있음
  • GCD(a,b) == GCD(b, a%b)
  • 시간복잡도 : O(lgN)
• 코드
  -- 반복문

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

-- 재귀함수

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

[최소공배수 - LCM]

• a ∗ b = GCD(a,b) ∗ LCM(a,b)
• 유클리드 호제법 이용

int LCM(int a, int b) {
  return (a * b) / GCD(a, b);
}