I want to find out an efficient method to calculate the largest divisor of a very big integer $b$ which can be up to $\large 2^{1000}$. That is, I want to find out an integer $a < b$, such that $a\mid b$ and a is the largest divisor. What's more, all integers, including the answer a, are in their binary representations. Thanks in advance.
Example:$ b = 101, a = 1$; $b = 110, a = 11.$
Best Answer
In theory, if you can find the smallest divisor and make the division this should give the largest divisor though this is basically running through a list of the smallest primes. For example, if $ 2 | b $ then the largest divisor will be $b/2$ as there isn't anything larger that would divide $b$ as there aren't any integer factors less than $2$ and greater than $1$. Thus, the challenge is to do a series of divisions though this is a bit of a brute force approach.