Encontrar el mayor divisor de un entero $b$ .

Question

Quiero encontrar un método eficiente para calcular el mayor divisor de un entero muy grande $b$ que puede ser de hasta $\large 2^{1000}$ . Es decir, quiero averiguar un número entero $a < b$ , de tal manera que $a\mid b$ y a es el mayor divisor. Además, todos los enteros, incluida la respuesta a, están en sus representaciones binarias. Gracias de antemano.

Ejemplo: $ b = 101, a = 1$ ; $b = 110, a = 11.$

Answer 1

En teoría, si puedes encontrar el divisor más pequeño y hacer la división, esto debería dar el divisor más grande, aunque esto es básicamente recorrer una lista de los primos más pequeños. Por ejemplo, si $ 2 | b $ entonces el mayor divisor será $b/2$ ya que no hay nada más grande que pueda dividir $b$ ya que no hay factores enteros menores que $2$ y mayor que $1$ . Por lo tanto, el reto es hacer una serie de divisiones, aunque esto es un poco de un enfoque de fuerza bruta.