[알고리즘] 유클리드 호제법
최대 공약수
- a,b (단, a>b)가 있다.
- a 를 b로 나웠을 때, 나머지(r)가 0인지 확인한다.
- 나머지(r) 0이 아니라면 a에 b를 넣고, b에는 r을 넣어서 2번 과정을 진행한다.
- 만약 나머지(r)이 0이라면 그 때의 b가 최대 공약수가 된다.
function gcd(a,b) {
let r = a % b;
return r ? gcd(b,r) : b;
}
최소 공배수
최소 공배수 * 최대공약수 = 0이 아닌 두 수의 곱임을 이용
=> 최소 공배수 = 0이 아닌 두 수의 곱 / 최대 공약수
function gcd(a,b) {
let r = a % b;
return r ? gcd(b,r) : b;
}
function lcm(a,b,gcd) {
return a * b / gcd;
}
Author And Source
이 문제에 관하여([알고리즘] 유클리드 호제법), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@psj8532/유클리드-호제법저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)