[알고리즘] 최대공약수와 최소공배수 C++ 구현

* 최대공약수(GCD : Greatest CommonDivisor)

* 최소공배수(LCM : Lowesr Common Multiplier)

 

 

유클리드 호제법

- 최대공약수를 구하기 위한 알고리즘

- 숫자 a, b의 최대공약수를 구하기

 

r = a를 b로 나눈 나머지로 설정하고 a, b의 값을 이동시킨다.

  a    b    r

152  68  20

68    20   8

20    8    4

8      4       -> 나누어 떨어짐 

 

--> 4가 최대공약수임

 a    b    r

152  68  20

68   20   8

20    8    4

8     4       -> 나누어 떨어짐 



--> 4가 최대공약수임

 

 

 

 

#include <iostream>
using namespace std;

int main()
{
  int a, b;
  cin >> a >> b;
  int GCD, LCM; // 최대공약수, 최소공배수
  int a2, b2; // a,b의 원본 저장

  a2 = a;
  b2 = b;
  
  while(1){
    int r = a % b;

    // 나누어 떨어짐 -> 최대공약수
    if(r == 0){
      GCD = b;
      break;
    }

    // 나누어 떨어지지 않았으면
    a = b;
    b = r;
  }

  a2 /= GCD;
  b2 /= GCD; 
  
  LCM = a2 * b2 * GCD; // 최소공배수 = a * b / GCD
  cout << GCD << " " << LCM << endl;
}