최소공배수(LCM)와 최대공약수(GCD)

• GCD

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

 

• LCM

LCM = (a*b)/GCD

GCD(a,b) = G라고 둠. a = Gx, b = Gy (x, y는 서로소인 정수) 성립. 따라서 a, b의 합집합은 G, x, y
즉, a*b의 최소공배수는 G*x*y. a*b = G*G*x*y이므로 LCM = (a*b)/G = (a*b)/GCD