Efficient algorithm to calculate all possible pair whose multiplication is a perfect quare I have two numbers $N$ and $M$.
I efficiently want to calculate how many pairs of $a$,$b$ are there such that $1 \leq a \leq N$ and $1 \leq b \leq M$ and $ab$ is a perfect square.
I know the obvious $N*M$ algorithm to compute this. But i want something better than that. I think it can be done in a better time may $\operatorname{O}(m+n)$ or something like that but calculating new pairs directly from previous pairs rather than iterating over all $a$ and $b$.
Thanks for any help in advance. A pseudo code will be more helpful.
 A: If you have a list of prime numbers up to $\max(M,N)$ here is one way to do it.
For each increasing $a$ from $1$ through $N$, find the prime decomposition of $a$. Multiply the primes (using exponent $1$) that have an odd exponent in the decomposition--call the result $c$. If $a \cdot c<M$ then $c$ is your smallest possible $b$ for this $a$; otherwise, there is no such $b$ for this $a$.
Then use a recursive algorithm to multiply $c$ by numbers $d$ made from prime decompositions with even exponents. This algorithm  would be something like: try $d=2^2$. If $a \cdot c \cdot d \le M$ then use it and use $3^2$ and so on. When that trial is done, use $d=2^4$, and so on.
The pseudo code would be a little tricky here, as for all recursion, but it should not be hard. My guess for this algorithm is order $N \cdot \ln(M)$.
A: Step 1:
Write a function $f$ that takes a perfect square $x$ and returns a list of all (or just the number of) possible pairs $(a,b)$ such that $ab = x$.
Step 2:
Have the function $f$ iterate over the squares of the integers $1$ to $n$, where
$n = \lfloor\sqrt{M*N}\rfloor$ and count the results as you go.
