1

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.

Mike Pierce
  • 18,938
user1465557
  • 121

2 Answers2

1

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)$.

Rory Daulton
  • 32,288
0

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.

Mike Pierce
  • 18,938