x এর মধ্যে জোড়ার সংখ্যা বের করার প্রোগ্রাম, যার গুণফল x এবং তারা পাইথনে কপ্রিম

ধরুন একটি ফাংশন f(x), যা (p, q) জোড়ার সংখ্যা গণনা করে, যেমন

• 1

• p এবং q হল coprime
• 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 থেকে sqr - 1 রেঞ্জের বেসের জন্য, করুন
  • আমি রেঞ্জ 1 থেকে ন্যূনতম বেস এবং ফ্লোর (n / base - base + 1) এর জন্য, কর
    • যদি বেসের gcd এবং i) 1 এর মত না হয়, তাহলে
      • পরবর্তী পুনরাবৃত্তির জন্য যান
    • গণনা :=গণনা + (n - i * ভিত্তি)/(বেস * বেস)
• রিটার্ন গণনা

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

ম্যাথ ইম্পোর্ট sqrt থেকে, gcddef solve(n):গণনা =0 sqr =int(sqrt(n)) + 1 পরিসরে বেসের জন্য(2, sqr):রেঞ্জে i এর জন্য(1, min(base, n) // বেস - বেস + 1)):যদি gcd(base, i) !=1:অবিরত গণনা +=(n - i * base) // (base * base) return countn =12print(solve(n)) 
ইনপুট
 
12
 
আউটপুট
 
3