수학에서 유클리드의 알고리즘은 두 수의 최대공약수(GCD)를 계산하는 방법으로, 나머지를 남기지 않고 두 수를 나누는 가장 큰 수입니다.
유클리드 알고리즘은 두 수의 최대공약수가 더 큰 수를 더 작은 수와의 차이로 대치해도 변하지 않는다는 원리를 기반으로 합니다.
예를 들어 21은 252와 105의 GCD(252 =21 × 12 및 105 =21 × 5)이고 동일한 숫자 21은 105와 252 - 105 =147의 GCD이기도 합니다.
이 교체는 두 숫자 중 더 큰 숫자를 줄이므로 이 프로세스를 반복하면 두 숫자가 같아질 때까지 더 작은 숫자 쌍이 연속적으로 생성됩니다. 이 경우 원래 두 숫자의 GCD입니다.
단계를 반대로 하면 GCD는 양수 또는 음의 정수를 각각 곱한 두 개의 원래 숫자의 합으로 표현할 수 있습니다(예:21 =5 × 105 + (−2) × 252).
우리는 두 개의 숫자를 취하고 GCD(최대공약수)를 계산하기 위해 Euclid 알고리즘을 사용하는 JavaScript 함수를 작성해야 합니다.
예시
다음은 코드입니다 -
const num1 = 252;
const num2 = 105;
const findGCD = (num1, num2) => {
let a = Math.abs(num1);
let b = Math.abs(num2);
while (a && b && a !== b) {
if(a > b){
[a, b] = [a - b, b];
}else{
[a, b] = [a, b - a];
};
};
return a || b;
};
console.log(findGCD(num1, num2)); 출력
다음은 콘솔의 출력입니다 -
21