x के बीच युग्मों की संख्या ज्ञात करने का कार्यक्रम, जिसका गुणन x है और वे Python में coprime हैं

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

• 1 <पी <=क्यू <=एक्स
• 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 जोड़े हैं।

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

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

उदाहरण

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

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