최대 공약수, 최소 공배수 한줄 코딩

알고리즘 출처 :

http://xn--299as6vb5i1je.com/interview/50

(상세한 내용은 위의 링크에서 확인 할 수 있습니다.)

GCD(2740, 1760) = GCD(1760, 2740) = 20이 되는 과정을 그림으로 나타낸 것

소스 코드 : 

< 기본 최대 공약수(GCD) 코드 >

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int gcd(int a, int b) {     while (1)     {         int r = a%b;         /*나머지가 0이라면*/           if (r == 0)             return b;           /*gcd(a,b) = gcd(b,r)*/         a = b;         b = r;     } }

Crocus

< 위의 내용을 줄인 코드 >

int gcd(int a, int b)
{
    if (b == 0) return a;
    else return gcd(b, a%b);
}
 

< C언어의 특성을 살린 코드 >

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

< 위의 내용을 이용한 최소 공배수(LCM) 코드 >

int lcm(int a, int b)
{
    return a*b/gcd(a,b);
}
 

< 예제 코드 >

#include<iostream>
using namespace std;
 
int gcd(int a, int b){return !b ? a : gcd(b, a%b);}
int lcm(int a, int b) { return a*b / gcd(a, b); }
int main()
{
    cout << gcd(10, 24) << "\n" << lcm(22,66);
}