पायथन में उन जोड़े की संख्या खोजने का प्रोग्राम जिनका गुणनफल x है और वे सह-अभाज्य हैं

मान लीजिए एक फ़ंक्शन f(x) है, जो (p, q) जोड़े की संख्या गिनता है, जैसे कि

• 1 < p <= q <= x
• p और q सह-अभाज्य हैं
• p * q = x तो यदि हमारे पास n है।

हमें रेंज 1 से n में सभी i के लिए f(x[i]) का योग खोजना है।

तो, यदि इनपुट 12 है, तो आउटपुट 3 होगा, क्योंकि x मान 1 से 12 तक होते हैं।

• जब x = 6, मान्य जोड़ा है (2, 3) तो f(6) = 1
• जब x = 10, मान्य जोड़ा है (2, 5) तो f(10) = 1
• जब x = 12, मान्य जोड़ा है (3, 4) तो f(12) = 1

तो कुल 3 जोड़े हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• count := 0
• sqr := n के वर्गमूल का पूर्णांक भाग + 1
• base को 2 से sqr - 1 तक की रेंज में, करें
  • i को 1 से base के न्यूनतम और floor of (n / base - base + 1) तक की रेंज में, करें
    • यदि base और i का gcd, 1 के समान नहीं है, तो
      • अगले पुनरावृत्ति के लिए जाएं
    • count := count + floor of (n - i * base)/(base * base)
• count लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

from math import sqrt, gcd def solve(n): count = 0 sqr = int(sqrt(n)) + 1 for base in range(2, sqr): for i in range(1, min(base, n // base - base + 1)): if gcd(base, i) != 1: continue count += (n - i * base) // (base * base) return count n = 12 print(solve(n))

इनपुट

12 

आउटपुट

3