GCD (महत्तम सांझा भाजक) – यूक्लिड का एल्गोरिथ्म
एल्गोरिथ्म के कई चक्र चलाने के बाद, हमें महसूस होता है कि कुछ अनावश्यक पुनरावृत्तियाँ हो रही हैं, और महत्तम सांझा भाजक (GCD) खोजने की यह प्रक्रिया को वास्तव में तेज़ किया जा सकता है।
घटाव के तरीके में, हम बड़े मान में से छोटे मान को बार-बार घटाते रहते हैं, जब तक कि नतीजा 0 न हो जाए या फिर GCD के बराबर न आ जाए। इसे तेज़ करने के लिए, हम बड़े मान को छोटे मान से भाग देकर मिलने वाले बाकी (remainder) का उपयोग कर सकते हैं। यानी, हम बार-बार बड़े मान को छोटे से भाग करके उसका शेषफल (modulo) लेते जाते हैं, जब तक कि शेष 0 न हो जाए। आख़िरी बार जो गैर-शून्य शेषफल मिलता है, वही इन दोनों संख्याओं का GCD होता है।
आप इसे इस तरह भी सोच सकते हैं कि घटाव की जगह पर مود्युलो ऑपरेशन एक अधिक असरदार तरीका है। घटाव में जहाँ आपको कई बार छोटा मान घटाना पड़ता है, वहीं विभाजन से बड़ी संख्या को तेज़ी से कम किया जाता है। इस प्रक्रिया में दोनों संख्याओं को उनके साझा भाजकों से बार-बार बांटा जाता है, जिससे आप अतिशीघ्र GCD तक पहुँच जाते हैं।
a, b = int(input()), int(input())
while a > 0 and b > 0: # यदि a या b शून्य है, तब दूसरा मान GCD होगा
a, b = b, a % b # gcd(a, b) और gcd(b, a % b) समान होते हैं
d = b if a == 0 else a # यदि a == 0 तो b GCD है, यदि b == 0 तो a GCD है
print('gcd:', d)यह एल्गोरिथ्म पहली बार ईसापूर्व 300 में लिखी गई यूक्लिड की पुस्तक में वर्णित हुआ था।
आइए इस एल्गोरिथ्म के कुछ उदाहरण देखें:
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ GCD = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ GCD = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ GCD = 1
इनपुट
इनपुट की एकमात्र पंक्ति में दो पूर्णांक
a और b होंगे (0 ≤ a, b ≤ )।आउटपुट
प्रोग्राम को
a और b का GCD प्रिंट करना चाहिए।Examples
Input | Output |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB