1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.