Gidhub BE Developer

GCD & LCM

2017-10-18
goodGid

GCD & LCM

유클리드 호제법

최대공약수와 최소공배수를 구할 두 수 중 큰 수와 작은 수를 정한 뒤

작은 수로 큰 수를 나누어 나머지를 구한다.

if ( 나머지 == 0 )
그때의 작은 수가 [최대공약수]이고,
원래 두 수를 곱한 값을 최대공약수로 나눈 값이 [최소공배수]이다.
else 
큰 수 = 작은 수
작은 수 = 나머지
나머지가 0이 될 때까지 반복

[1] GCD & LCM Code


#include<iostream>
using namespace std;

pair<int,int> gcdAndlcm(int a, int b){
    int big, small;
    int mok, nmg, gcd, lcm;
    
    if ( a >= b){
        big = a;
        small = b;
    }
    else{
        big = b;
        small = a;
    }
    while (1) {
        mok = big / small;
        nmg = big - mok * small;
        if (nmg == 0){
            gcd = small;
            lcm = a * b / gcd;
            return make_pair(gcd, lcm);
        }
        big = small;
        small = nmg;
    }
}

int main(){
    int a,b;
    cin >> a >> b;
    pair<int, int> p;
    p = gcdAndlcm(a, b);
    cout << "gcd : " << p.first << endl;
    cout << "lcm : " << p.second << endl;
    
    return 0;
}



[2] GCD & LCM Code


int gcd(int a,int b){ //반복문을 이용한 방법
    int mod = a % b;
    while(mod > 0)
    {
        a = b;
        b = mod;
        mod = a % b;
    }
    return b;
}
 
int gcd(int a,int b){ //재귀 함수형
    if( a % b == 0 )
        return b;
    else
        return gcd(b, a % b);
}
 
int gcd(int a, int b){ //삼항 연산자 축약형 
    return (a % b == 0 ? b : gcd(b,a%b));
}

lcm = a * b / gcd;


[3] GCD & LCM Code


void gcdlcm(int a,int b){
    if(a > b){
        swap(a,b);
    }
    
    for(int i = a; i > 0; i--){
        if(((a%i) == 0) && ((b%i) == 0)){
            printf("GCD : %d \n", i );
            printf("LCM : %d \n", (a*b)/i);
            break;
        }
    }
}


Next : String Check

Comments

Content