최대공약수 최소공배수 구하기(C++)

두 자연수를 입력받고 최대공약수 최소공배수 순으로 출력하라.



최대공약수는 뉴클리드 호제법으로 구할 수 있다.

서로다른 두 자연수 a,b의 최대공약수가 r이면 ab는 다음과 같이 나타낼 수 있다,
a=cxr, b=dxr

여기서 당연히 c와 d는 서로소인 자연수가 된다.
따라서 a,b중 큰 수에서 작은 수를 빼고 또 그 뺀 값과 작은수를 비교해서 더 작은수를 빼주고 이런 과정을 반복해서 0이될때 가장 마지막 숫자가 최대 공약수가 된다.

최소공배수는 두수의 곱에 최대공약수를 나누면 나온다.


#include <iostream>
#include <windows.h>
#include <algorithm>
using namespace std;
int main(){
   
    int a,b,g,l;
    bool isgcd=false;
   
    cin>>a>>b;
   
    l=a*b;
   
    while(!isgcd){
                  if(b>a)swap(a,b);
                 
                  a=a-b;
                 
                  if(a==0){
                           g=b;
                           isgcd=true;
                  }
    }
   
    l/=g;
    cout << g << endl << l << endl;
        
    system("PAUSE");
   
    return 0;
   
}


실행결과

24 18
6
72
Press any key to continue . . .