최대공약수와 최소공배수의 '유클리드 호제법`

유클리드 호제법

• 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘

1. 두 수 중에서 큰 수를 작은 수로 나눈다.
2. 만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다.
3. 만약 나머지가 0 이 아니라면, 작은 수를 다시 나머지로 나눈다.
4. 이를 반복해서 나머지가 0 이 될 때, 그 수가 바로 두 수의 최대공약수이다.

function gcd(a, b) {

    const remainder = a % b;

    if (remainder === 0) return b;

    return gcd(b, remainder);

}

🐷
이전에 했던 방법은 for, while 반복문을 사용하여 최대공약수를 구했는데, 주어진 두 수의 차이가 크다면 반복 횟수가 너무 많아지기 떄문에 좋지 못한 코드이다.

유클리드 호제법을 사용하면 5번 이하로 끝날것이다.