একটি ধনাত্মক সংখ্যা M খুঁজুন যেমন gcd(N^M,N&M) পাইথনে সর্বাধিক

ধরুন আমাদের একটি সংখ্যা N আছে, আমাদের একটি ধনাত্মক সংখ্যা M খুঁজে বের করতে হবে যেমন gcd(N^M, N&M) যতটা সম্ভব বড় এবং m

সুতরাং, যদি ইনপুট 20 এর মত হয়, তাহলে আউটপুট হবে 31

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

যদি bit_count(n) 0 এর মত হয়, তাহলে
- আমি 2 থেকে int(n) এর বর্গমূল + 1 রেঞ্জের জন্য, কর
  - যদি n mod i 0 এর মত হয়, তাহলে
    - রিটার্ন int(n/i)
অন্যথায়,
- val :=0
- p :=
- dupn :=n
- যখন n অ-শূন্য, do
  - যদি (n AND 1) 0 এর মত হয়, তাহলে
    - val :=val + p
  - p :=p * 2
  - n :=n>> 1
- রিটার্ন gcd(val XOR dupn, val AND dupn)
প্রত্যাবর্তন 1

উদাহরণ

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

from math import gcd, sqrt
def bit_count(n):
   if (n == 0):
      return 0
   else:
      return (((n & 1) == 0) + bit_count(n >> 1))
def maximum_gcd(n):
   if (bit_count(n) == 0):
      for i in range(2, int(sqrt(n)) + 1):
         if (n % i == 0):
            return int(n / i)
   else:
      val = 0
      p = 1
      dupn = n
      while (n):
         if ((n & 1) == 0):
            val += p
         p = p * 2
         n = n >> 1
      return gcd(val ^ dupn, val & dupn)
   return 1
n = 20
print(maximum_gcd(n))