गणित में, यूक्लिड का एल्गोरिथ्म, दो संख्याओं के सबसे बड़े सामान्य भाजक (GCD) की गणना करने की एक विधि है, सबसे बड़ी संख्या जो दोनों को बिना शेष छोड़े विभाजित करती है।
यूक्लिडियन एल्गोरिथम इस सिद्धांत पर आधारित है कि दो संख्याओं का सबसे बड़ा सामान्य भाजक नहीं बदलता है यदि बड़ी संख्या को उसके अंतर से छोटी संख्या से बदल दिया जाए।
उदाहरण के लिए, 21, 252 और 105 का जीसीडी है (252 =21 × 12 और 105 =21 × 5 के रूप में), और वही संख्या 21 भी 105 और 252 - 105 =147 की जीसीडी है।
चूंकि यह प्रतिस्थापन दो संख्याओं में से बड़ी संख्या को कम कर देता है, इस प्रक्रिया को दोहराने से दो संख्याओं के बराबर होने तक क्रमिक रूप से छोटे जोड़े मिलते हैं। जब ऐसा होता है, तो वे मूल दो संख्याओं की GCD होती हैं।
चरणों को उलट कर, GCD को दो मूल संख्याओं के योग के रूप में व्यक्त किया जा सकता है, जिनमें से प्रत्येक को एक धनात्मक या ऋणात्मक पूर्णांक से गुणा किया जाता है, जैसे, 21 =5 × 105 + (−2) × 252।
हमें एक जावास्क्रिप्ट फ़ंक्शन लिखना है जो दो नंबर लेता है और यूक्लिड के एल्गोरिदम का उपयोग उनके जीसीडी (सबसे बड़ा सामान्य भाजक) की गणना करने के लिए करता है
उदाहरण
निम्नलिखित कोड है -
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