Start by checking whether $A$ divides $B$. If it doesn't, we're done, the answer is $0$. If it does, let $C = \frac{B}{A}$. The numbers you're looking for are all of the form $AM$ where $M$ divides $C$, so all you need is the number of divisors of $C$.
Let $C=p_0^{c_0}...p_n^{c_n}$ be the prime decomposition of $C$. The number of dividers of $C$ is then $\prod\limits_{i}(c_i+1)$, so the problem boils down to the prime decomposition of $C$, which can indeed be done in $O(\sqrt{C})$:
residue = C
divider = 2
number_of_prime_dividers = 0
factors = empty array
while((residue >= divider) and (divider <= sqrt(C))
{
if(divider divides residue)
{
number_of_prime_dividers = number_of_prime_dividers +1
factors[number_of_prime_dividers] = 0
}
while( divider divides residue )
{
residue = residue / divider
factors[number_of_prime_dividers] = factors[number_of_prime_dividers] + 1
}
divider = divider + 1
}
if(residue != 1)
{
number_of_prime_dividers = number_of_prime_dividers +1
factors[number_of_prime_dividers] = 1
}
This algorithm works because by construction, every time divider
divides residue
, then it means that divider
is prime (if divider
is composite then all the factors of divider
are strictly smaller than divider
and thus have already been removed from residue
). Once we reach sqrt(C)
, if residue != 1
we know that residue
is prime, which concludes the decomposition.