जावास्क्रिप्ट में यूक्लिडियन एल्गोरिदम से GCD निकालना

गणित में, यूक्लिड का एल्गोरिदम, दो संख्याओं के महत्तम सामान्य भाजक (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 (महत्तम सामान्य भाजक) की गणना के लिए यूक्लिड के एल्गोरिदम का उपयोग करता है।

उदाहरण

निम्नलिखित कोड है -

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