최대공약수, 최소공배수 구하기

 정의

우선 생각이 잘 안날 수도 있으니 최대공약수와 최소공배수의 개념부터 설명하겠습니다.

최대공약수 - 공통으로 가지고 있는 약수 중 가장 큰수

최대공배수 - 두 수의 공통인 배수 중 가장 작은 수

알고리즘 문제 분석

◎ 최대공약수 구하기

두 수를 입력받고 둘중 큰 수를 작은 수로 나누었을때 나머지가 0이면 큰 수가 바로 최대공약수이다. 

만약 나머지가 0이 아니라면 작은수를 큰수라고 하고 나머지를 작은수라고 두어 나누었을때 0 이 나올때까지 반복해 최대공약수를 구하면 된다.

◎ 최소공배수 구하기

최소공배수는 두 수를 곱하고 최대공약수로 나누면 된다.

구현

#include <iostream>

#include <string>

using namespace std;

int main() {

    int a,b;

    int big, small, mok, nmg;

    int gcm, lcm;

    

    cin >> a >> b;

    if( a>=b) {

        big = a;

        small = b;

    }else{

        big = b;

        small = a;

    }

    while(1) {

        mok = big / small;

        nmg = big % small;

        if ( nmg == 0 ){

            gcm = small;

            lcm = a * b / gcm;

            cout << "gcm : "<<gcm <<" lcm: " << lcm;

            break;

        }

        big = small;

        small = nmg;

        

    }

    return 0;

}