Answer:

The Approach:
What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q

---

More Questions and Answers @ Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)

Delivered instantly as a PDF via email. For Software Engineers & SDETs      

·         150 programming interview questions and answers

·         5 proven approaches to crack algorithm questions

·         10 mistakes candidates make, and how to avoid them.

·         How to prepare for technical and behavioral questions without wasting your time!

30 Day Money Back Guarantee: Don't love the book? We'll give you your money back!
 

More Info

---