[c++] 최대공약수 최소공배수 알고리즘 (gcd,lcm 구하기)

안녕하세요👋
이번에는 매일매일 까먹는 gcd(최대공약수) lcm(최소공배수) 구하는 방법을 작성해보겠습니다. 쓸때마다 헷갈리는데 하다보면 또 바로 즉석해서 구현이 되는 것들 인데요 혹시나 잊어버리지 않기위해 한번 정리해서 블로그에 작성해두려고 합니다.

📝gcd(최대공약수)

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

📑lcm(최소공배수)

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

둘다 한줄이면 끝나는 코드지만 재귀로 정말 잘짜여진 코드라는것을 알 수 있습니다. 사실 너무 유명한 코드라 한번씩은 다들 봣을것 같은데 막상 쓸때는 a,b인지 b,a인지 a%b인지 a/b인지 기억이 안나서 또 차근차근 계산해보게 되는 코드인데요.
최대공약수의경우 b가 0이될때 a는 그전 a%b가 되기전 a값의 약수였다는 것을 알 수 있습니다 이게 처음 나올 때 a가 최대공약수가 되겟죠
최송공배수는 두 수를 곱한뒤 두 수의 최대공약수로 나누어주면 됩니다 a b 두수를 소인수분해 했다고 생각하고 곱하면 최대공약수만 2번 곱해지게 되겠죠 따라서 최소공배수는 a*b/gcd(a,b)로 간단하게 구할 수 있습니다
알아두면 분명 쓸모가 있고 유용한 공식이니 꼭 잊어버리지 말아야 겠습니다

긴글 봐주셔서 항상 감사합니다 앞으로도 유용한 내용을 많이 공유하겠습니다 그럼 안녕 👋