পাইথনে সংখ্যাগুলিকে নন-কপ্রাইম করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন গণনা করার প্রোগ্রাম?

ধরুন আমাদের দুটি সংখ্যা A এবং B আছে। এখন প্রতিটি ক্রিয়াকলাপে, আমরা যেকোনো একটি সংখ্যা নির্বাচন করতে পারি এবং এটিকে 1 দ্বারা বৃদ্ধি করতে পারি বা এটি 1 দ্বারা হ্রাস করতে পারি। আমাদের সর্বনিম্ন সংখ্যক ক্রিয়াকলাপ খুঁজে বের করতে হবে যাতে সর্বশ্রেষ্ঠ সাধারণ ভাজক A এবং B এর মধ্যে 1 নয়।

সুতরাং, যদি ইনপুটটি A =8, B =9 এর মত হয়, তাহলে আউটপুট হবে 1, যেহেতু আমরা 9 নির্বাচন করতে পারি তারপর এটিকে বাড়িয়ে 10 করতে পারি, তাই 8 এবং 10 কপ্রিম নয়।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

যদি a এবং b এর gcd 1 এর মত না হয়, তাহলে
- রিটার্ন 0
যদি a জোড় বা b জোড় হয়, তাহলে
- রিটার্ন 1
অন্যথায়,
- যদি a + 1 এবং b এর gcd 1 বা a - 1 এর gcd না হয় এবং b - 1 বা a andb এর gcd - 1 একই না হয় বা a এবং b + 1 এর gcd একই না হয় 1, তারপর
  - রিটার্ন 1
- অন্যথায়,
  - রিটার্ন 2

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

উদাহরণ

from math import gcd

class Solution:
   def solve(self, a, b):
      if gcd(a, b) != 1:
         return 0
      if a % 2 == 0 or b % 2 == 0:
         return 1
      else:
         if (gcd(a + 1, b) != 1 or gcd(a - 1, b) != 1 or gcd(a, b - 1) != 1 or gcd(a, b + 1) != 1):
            return 1
      else:
         return 2

ob = Solution()
A = 8
B = 9
print(ob.solve(A, B))

ইনপুট

8,9