找到一个正数M，使gcd（N ^ M，N＆M）在Python中最大

假设我们有一个数字N，我们必须找到一个正数M，以使gcd（N ^ M，N＆M）尽可能大并且m <n。我们还将返回由此获得的最大gcd。

因此，如果输入为20，则输出为31

为了解决这个问题，我们将遵循以下步骤-

• 如果bit_count(n)与0相同，则

• 如果n mod i等于0，则

• 返回int（n / i）

• 对于范围2到int（(n)的平方根）+1的i，执行

• 除此以外，

• 如果（n AND 1）等于0，则

• p：= p * 2

• n：= n >> 1

• 值：=值+ p

• 值：= 0

• p：=

• 杜邦：= n

• 当n不为零时，

• 返回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))

输入值

20

输出结果

31