यह जांचने का सबसे तेज़ तरीका क्या है कि दो दिए गए नंबर coprime हैं?

Question

एक तरह से उनके gcd की गणना और जाँच अगर यह होता है 1.

वहाँ कुछ तेजी से रास्ता है के लिए है?

Answer 1

यूक्लिडियन एल्गोरिदम (gcd की गणना) बहुत तेज है। जब [1, n] से यादृच्छिक रूप से दो संख्याओं को समान रूप से खींचा जाता है, तो उनके gcd की गणना करने के लिए चरणों की औसत संख्या O(log n) है। प्रत्येक चरण के लिए आवश्यक औसत गणना समय अंकों की संख्या में वर्गबद्ध है।

ऐसे विकल्प हैं जो कुछ हद तक बेहतर प्रदर्शन करते हैं (यानी, प्रत्येक चरण अंकों की संख्या में subquadratic है), लेकिन वे केवल बहुत बड़े पूर्णांक पर प्रभावी हैं। उदाहरण के लिए, On Schönhage's algorithm and subquadratic integer gcd computation देखें।

Answer 2

यदि आप ऐसी मशीन पर चल रहे हैं जिसके लिए विभाजन/शेष बदलावों की तुलना में काफी महंगा है, तो binary GCD पर विचार करें।