Efficient algorithm to calculate all possible pair whose multiplication is a perfect quare

Question

I have two numbers N and M. I efficiently want to calculate how many pairs of a,b are there such that 1<=a<=N and 1<=b<=M and a*b is a perfect square.

I know the obvious N*M algorithm to compute this. But i want something better than that. Thanks for any help in advance. A pseudo code will be more helpful.

EDIT : I think it can be done in a better time may O(m+n) or something like that but calculating new pairs directly from previous pairs rather than iterating over all a and b.

Answer 1

I would go for a way using prime decompositions. Get a hold of all the prime numbers between 1 and max(N,M), and let us call them the (p0, p1, ... pn)

Then any number a <= N and b <= M can be written as and , for i from 1 to n, where the ai and bi can be any positive integer or 0.

Then, any product a*b can be written as , and the caracterization of a perfect square in that writing would be that all the (ai+bi) need to be even (0 is even, for the record).

Then you somehow need to iterate over all the (ai) such that a <= N, and for each set of (ai) generate all the (bi) such that b <= M and all the (ai+bi) are even.

Not sure that's the anywhere near efficient, but should work just fine.

Answer 2

My approach would be this:

1. for s is quare and s <= N*M

   1. Do a prime factorization of s.

   2. iterate over the partitions of this prime factorization and check which ones fullfill your requirement

Iterating over the possible partitions may be a bit tricky, but I'm quite certain that this is the most efficient approach that is possible.

Iterating over square numbers, on the other hand, is trivial:

for(int i = 0, square = 0; /*whatever*/; square += 2*i++ + 1)